poj1716,

## Problem:

Integer Intervals
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8722 Accepted: 3644
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`
Source
CEOI 1997

## Source Code:

#include<stdio.h>
#include<algorithm>
using namespace std;

struct tt
{
int left,right;
bool valid;     //Need to be satisfied or not;
}inter;
bool cmp(tt p,tt q)
{
if(p.left<q.left||(p.left==q.left&&p.right>q.right))
return true;
return false;
}

void init(int n)
{
int i;
int a,b;
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
inter[i].valid=true;
inter[i].left=a;
inter[i].right=b;
}
}

void Cal(int n)
{
int count=2;
int i,j;
sort(inter,inter+n,cmp);
//try to reduce the one that has larger extension,leave the small one be covered.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
if(inter[j].left<=inter[i].left&&inter[j].right>=inter[i].right)
inter[j].valid=false;
}
}
//*********************************************************
//for(i=0;i<n;i++)
//  printf("%d %d %d\n",inter[i].left,inter[i].right,inter[i].valid);
//*********************************************************
int p,q;
//Greedy part;
//Find the first value of p and q which is valid;
for(i=0;i<n;i++)
{
if(inter[i].valid==false)
continue;
p=inter[i].right;
q=inter[i].right-1;
break;
}
for(;i<n;i++)
{
//printf("%d %d\n",q,p);
//p,q is the share part of the coheresive sets;
if(q>=inter[i].left||inter[i].valid==false)
continue;
//p is ,but q is not;
else if(p>=inter[i].left)
{
count++;
q=p;
p=inter[i].right;
continue;
}
//Neither of p and q is the share part of two sets;
else
{
count+=2;
p=inter[i].right;
q=inter[i].right-1;
}
}
printf("%d\n",count);
}

int main()
{
int n;
scanf("%d",&n);
init(n);
Cal(n);
return 0;
}