1615: 找区间
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 284 Solved: 117
[Submit][Status][Web Board]
Description
在X轴上有n个闭区间，去掉尽可能少的区间使剩下的区间都不相交
Input
多组测试数据
第一行输入n（n<=1000）
接下来n行每行两个数a,b代表闭区间的两个端点。
（a,b<=1000000）
Output
输出最小的删除的区间数
Sample Input
3
10 20
15 10
20 15
Sample Output
2
【分析】贪心算法的应用——选择不相交区间问题；
- 将一系列点按区间尾端点升序排序，注意输入的两点没有顺序，所以如果左端点大于右端点要先交换一下（swap()）；
- 将最小的右端点赋值给t，遍历时如果下一个区间的左端点大于t则计数器自加；
- 因为题目求的是删掉的，也就是总区间数（n）减去不想交区间数。
#include<bits/stdc++.h>
using namespace std;
struct node{int st;int ed;
}a[1005];
bool cmp(node x,node y)
{return x.ed<y.ed;
}
int main()
{int n;while(~scanf("%d",&n)){for(int i=0;i<n;i++){int aa,bb;cin>>aa>>bb;if(aa>bb)swap(aa,bb);a[i].st=aa;a[i].ed=bb;}sort(a,a+n,cmp);int t=a[0].ed;int ans=1;for(int i=1;i<n;i++){if(a[i].st>t)ans++,t=a[i].ed;}cout<<n-ans<<endl;}return 0;
}