POJ1717总结

Integer Intervals

题目来源

Description

An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.
Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.

Input

The first line of the input contains the number of intervals n, 1 <= n <= 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.

Output

Output the minimal number of elements in a set containing at least two different integers from each interval.

Sample Input

4
3 6
2 4
0 2
4 7

Sample Output

4

我的代码

贪心思路：对所有整数区间按照结束端点的值升序排序，那么对于第i个区间，如果其与第i+k（k>0）个区间有重合的部分，重合必然包括第i个区间的最后若干个元素。那么对于每一个区间，优先选择尾部的两个元素即可。

在遍历每一个区间的过程中，都要考察上一个区间选取的两个数。如果当前区间包含了两个数，那么就继续引用这两个数即可（若重新选择第三个数，假如第三个数不在之后的任何区间上，结果只会更大，如果在某个区间k上，那么第三个数就是即将在k区间上要选择的，不影响结果）；如果只包含这一个数，那么当前区间的两个数分别是从前一个区间包含的数（是较大的那个），和当前序列的最后一个元素；如果一个都不包含，就选择当前区间的最后两个元素。初始化为第一个区间的最后两个元素。

#include<stdio.h>
#include<algorithm>

using namespace std;

struct interval{
	int begin,end;
};

bool cmp(interval a,interval b)
{
	return a.end<b.end;
}

int main()
{
	int n,ans=2,num1,num2;
	scanf("%d",&n);
	interval intervals[10000];
	for (int i=0;i<n;i++)
	{
		scanf("%d%d",&intervals[i].begin,&intervals[i].end);
	}
	sort(intervals,intervals+n,cmp);
	num1=intervals[0].end-1;
	num2=intervals[0].end;
	for (int i=1;i<n;i++)
	{
		if (intervals[i].begin<=num1) continue;
		else if (intervals[i].begin<=num2) 
		{
			ans++;
			num1=num2;
			num2=intervals[i].end;
		}
		else
		{
			ans=ans+2;
			num1=intervals[i].end-1;
			num2=intervals[i].end;
		}
	}
	printf("%d\n",ans);
	return 0;
}

反思

我一开始还是想的太复杂了。