输入
第1行:1个数N,线段的数量(2 <= N <= 10000)
第2 - N + 1行:每行2个数,线段的起点和终点(-10^9 <= S,E <= 10^9)
输出
输出最多可以选择的线段数量。
输入示例
3
1 5
2 3
3 6
输出示例
2
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct {
long long tb;
long long te;
} TIME;
TIME TIME_TABLE[10007];
bool cmp(TIME a,TIME b)
{
return (a.te < b.te);
}
int N;
int main()
{
int cnt;
int ans;
while(~scanf("%d",&N))
{
if(N == 0) break;
//默认的ans是1
ans = 1;
cnt = 0;
//将存放时间的数组排序
for(int i = 0;i < N;i++)
scanf("%ld%ld",&TIME_TABLE[i].tb,&TIME_TABLE[i].te);
sort(TIME_TABLE,TIME_TABLE+N,cmp);
for(int i = 1;i < N;i++) {
//如果有序数组(按照结束时间从小到大排序)
//的第i项的开始时间比目前选定的一项(cnt)的结束时间要晚
//那么就把它当做下一个cnt,然后ans计数加一
if(TIME_TABLE[i].tb >= TIME_TABLE[cnt].te) {
cnt = i;
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
结果最后是WA。。各位大神帮忙看看