时间限制: 2 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
在一个数轴上有n条线段,现要选取其中k条线段使得这k条线段两两没有重合部分(端点可以重合),问最大的k为多少。
输入描述 Input Description
输入格式
输入文件的第1行为一个正整数n,下面n行每行2个数字ai,bi,描述每条线段。
输出描述 Output Description
输出格式
输出文件仅包括1个整数,为k的最大值
样例输入 Sample Input
3
0 2
2 4
1 3
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
数据范围
对于20%的数据,n≤10;
对于50%的数据,n≤1000;
对于70%的数据,n≤100000;
对于100%的数据,n≤1000000,0≤ai<bi≤1000000。
我们首先按他的结束顺序排序
然后比较每一个与他前面已放置的是否冲突就可以
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 struct node
7 {
8 int x;
9 int y;
10 }a[1000001];
11 int num=1;
12 int comp(const node & a,const node & b)
13 {
14 return a.y<b.y;
15 }
16 int main()
17 {
18 int n;
19 scanf("%d",&n);
20 for(int i=1;i<=n;i++)
21 {
22 scanf("%d%d",&a[num].x,&a[num].y);
23 num++;
24 }
25 sort(a+1,a+num,comp);
26 int tot=0;
27 int last=a[1].y;
28 for(int i=1;i<=num-1;i++)
29 {
30 if(a[i+1].x>=last)
31 {
32 tot++;
33 last=a[i+1].y;
34 }
35 }
36 printf("%d",tot+1);
37 return 0;
38 }