Description
Input
Output
Sample Input
| input | output |
|---|---|
5 3 4 1 5 6 7 4 5 1 3 |
3 |
大意：找出最大的不相交的区间的个数
原文题解 传送门
贪心：
对于所有的时间对于end进行排序，因为结束的越早后面的就越可以加进来，每一步都是最优的
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct edge{
int b;
int e;
}a[100010];
bool cmp(edge i, edge j){
if(i.e == j.e)
return i.b < j.b;
return i.e < j.e;
}
int main()
{
int n;
while(~scanf("%d",&n)){
for(int i = 1; i <= n ;i++)
scanf("%d%d",&a[i].b,&a[i].e);
sort(a+1,a+n+1,cmp);
int t = 0;
int ans = 0;
for(int i = 1; i <= n; i++){
if(a[i].b >= t){
t = a[i].e + 1;
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
DP：
URAL1203——DPor贪心——Scientific Conference
原文：http://www.cnblogs.com/zero-begin/p/4483394.html