三哥无聊的在纸上划着线条，队友不能容忍，于是借机给他出了一个简单的问题，让他把自己画 的n线条选择一部分摆到数轴上，且两两没有重合,然后问他最大的摆放数量k
输入
第一行为一个正整数 n； 在接下来的 n 行中，每行有 2个数 ai,bi描述每条线段。 n, ai, bi(0 < n, ai, bi ≤ 106 )
输出
输出一个整数，为 k的最大值。
输入样例
3
0 2
2 4
1 3
输出样例
2
这是我HPU暑期ACM集训的时候我们学长自己出的题，我们自己的服务器判题，但是当时出了很多BUG
但是总的来说让我们体验了一次区域赛的形式，最后的滚榜还是很刺激的！！！这是个简单的贪心问题
贪心：
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct stu //结构体存下在数轴上线段的起点和终点的位置 { int l; int r; }data[1000000+10]; bool cmp(stu x,stu y ) //把这写点的终点按照升序的方法排序； { return x.r<y.r; } int main () { int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d",&data[i].l,&data[i].r); } sort(data,data+n,cmp); //排序 int jishu= 1; int right= data[0].r; //让第一个终点等于我们输入的第0个，也就是第一个 for(int i = 1;i<n;i++) { if(data[i].l>=right) //如果 我们找到了起点的数字大于终点的大小 { //我们的计数器就+1 jishu++; // 然后把交换位置 让后面的一个成 r right=data[i].r; } } printf("%d",jishu); return 0; }
