POJ1716 Integer Intervals

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 13984		Accepted: 5943

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

Sample Output

Source

CEOI 1997

题目和POJ1201相同。

由于这次区间内的数的个数固定为2，所以可以使用贪心解法。将区间按右端点从小到大排序，每次能不加点就不加，必须加的话就加在区间最右面，并累计答案数。

 1 /**/
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 using namespace std;
 8 const int mxn=50000;
 9 struct area{
10     int l,r;
11 }a[mxn];
12 int n;
13 int ans,f,s;
14 int cmp(area a,area b){
15     if(a.r!=b.r)return a.r<b.r;
16     return a.l<b.l;
17 }
18 int main(){
19     scanf("%d",&n);
20     int i,j;
21     for(i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);
22     sort(a+1,a+n+1,cmp);
23     ans=2;f=a[1].r;s=a[1].r-1;
24     for(i=2;i<=n;i++){
25         if(f<a[i].l){
26             ans+=2;
27             f=a[i].r;
28             s=a[i].r-1;
29             continue;
30         }
31         if(s<a[i].l){
32             ans++;
33             if(f>a[i].r-1)    s=a[i].r-1;
34             else s=f;
35             f=a[i].r;
36             continue;
37         }
38         if(f>a[i].r)f=a[i].r;
39     }
40     printf("%d
",ans);
41     return 0;
42 }