【贪心】【codevs】1214 线段覆盖

http://codevs.cn/problem/1214/

我去这个题。。。wa的我都没脾气了。。。

我写while（~scanf（“%d”， &n））竟然是不对的。。。

这个程序你妹多次输入是不能结束的？？？？！！！！！！

改成scanf输入一次竟然就对了。。。。整个人都不好了。。。。

就是一个贪心，做法和《今年暑假不AC》是一样的

按照结束时间（线段末尾排序），依次添加不重叠的线段即可

因为已经先按照结束时间排序，结束时间相同的按照开始时间排序，这样选择最早结束的一定不会使结果更糟。例如 1 4 和 1 2， 2 4虽然1  2， 2 4看上去是比1 4度一组但是因为2已经在之前被扫过了所以是不会出现这种情况的。。。

啊本来不用解释的但是因为输入的问题所以生气的再解释一遍！= =

#include<bits/stdc++.h>
using namespace std;typedef struct line{int x, y;bool operator < (const line& l) const{if(y == l.y) return x < l.x;else return y < l.y;}
}line;line l[1005];int main(){int n;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d%d", &l[i].x, &l[i].y);if(l[i].x > l[i].y) swap(l[i].x, l[i].y);}sort(l, l+n);int ans = 0;int tr = -1000;for(int i = 0; i < n; i++){if(l[i].x >= tr){tr = l[i].y;ans++;}}printf("%d\n", ans);return 0;
}