本文主要是介绍1089 Intervals，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意:
给定n个区间,求他们的并,用最少的区间表示
考虑2个区间的位置关系,只有5种
先按区间左端点增序排
从左到右O(n)扫一遍
第i个区间右端点比当前处理区间右端点大,而且他们相交,则更新当前处理区间的右端点
第i个区间和当前处理区间不交,则产生新区间,输出,并更新当前处理区间的左右端点
- //4471891_AC_125MS_792K
- /**********************************************************************
- * Online Judge : POJ
- * Problem Title : Intervals
- * ID : 1089
- * Date : 12/10/2008
- * Time : 7:47:11
- * Computer Name : EVERLASTING-PC
- ***********************************************************************/
- #include<iostream>
- #include<algorithm>
- using namespace std;
- #define MAXN 50000
- struct Interval
- {
- int s,e;
- };
- bool cmp(Interval a,Interval b)
- {
- return a.s<b.s;
- }
- Interval a[MAXN];
- int n,ss,ee;
- int main()
- {
- //freopen("in_1089.txt","r",stdin);
- while (scanf("%d",&n)!=-1)
- {
- for (int i=0;i<n;++i)
- {
- scanf("%d%d",&a[i].s,&a[i].e);
- }
- sort(a,a+n,cmp);
- ss=a[0].s;
- ee=a[0].e;
- for (int i=1;i<n;++i)
- {
- if (a[i].s<=ee&&ee<a[i].e)
- {
- ee=a[i].e;
- }
- else if(ee<a[i].s)
- {
- printf("%d %d/n",ss,ee);
- ss=a[i].s;
- ee=a[i].e;
- }
- }
- printf("%d %d/n",ss,ee);
- }
- return 0;
- }
这篇关于1089 Intervals的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
