Integer Intervals

 

描述

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.

输入

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 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 <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#define sf(a) scanf("%d\n",&a)
#define rep(i,a,b) for(i=a;i<=b;i++)
#define e 1e-8
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
const int idata=1e4+5;

int i,j,k;
int judge,flag,temp;
//vector<ll>step(idata);
ll step[idata];
//int dp[idata];
ll n,m,t,x,y;
ll maxx=-inf,minn=inf;
ll cnt,len,ans,sum;
int l[idata],r[idata];
pair<int ,int>p[idata];
string s;
int cmp[100000];

int main()
{
    while(cin>>n)
    {
        for(i=1;i<=n;i++)
        {
            cin>>l[i]>>r[i];
            p[i].first=r[i];
            p[i].second=l[i];
        }
        sort(p+1,p+1+n);

        int left=p[1].first-1;
        int right=p[1].first;
        sum=2;
        for(i=2;i<=n;i++)
        {
            if(p[i].second>right)
            {
                sum+=2;
                left=p[i].first-1;
                right=left+1;
            }
            else if(right>=p[i].second&&left<p[i].second)
            {
                sum++;
                left=right;
                right=p[i].first;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}