已知数轴上0<N<10000条线段。每条线段按照端点Ai和Bi(Ai<>Bi,i=1..N)定义。端点坐标在(-999,999)内,坐标为整数。有些线段可能相交。编程实现删除最少数目的线段,使得余下的任意两条线段不相交。
输入格式:
第一行为一整数N。接下来有N行,每行包含两个整数 (Ai 和 Bi), 用空格隔开。
输出格式:
整数p,即删除后余下的线段数。
输入样例#1:
3
6 3
1 3
2 5
输出样例#1:
2
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[10001];
11 int comp(const node & a , const node & b)
12 {
13 return a.y<b.y;
14 }
15 int main()
16 {
17 int n;
18 scanf("%d",&n);
19 for(int i=1;i<=n;i++)
20 {
21 scanf("%d%d",&a[i].x,&a[i].y);
22 if(a[i].x>a[i].y)
23 swap(a[i].x,a[i].y);
24 }
25
26 sort(a+1,a+n+1,comp);
27 int last=-10000;
28 int ans=0;
29 for(int i=1;i<=n;i++)
30 {
31 if(a[i].x>=last)
32 {
33 ans++;
34 last=a[i].y;
35 }
36 }
37 printf("%d",ans);
38 return 0;
39 }