# 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.

```4
3 6
2 4
0 2
4 7
```

`4`

### 我的代码

``````#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;
}``````