poj_1716_IntegerIntervals.cpp

Problem Links:

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

Solution:

Source Code:

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

struct tt
{
    int left,right;
    bool valid;     //Need to be satisfied or not;
}inter[10001];
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;
}