区间覆盖（nlogn）

admin

[code=Cpp width=700px]#include<iostream>
using namespace std;
struct abc
{
    int s,e;
}a[20];
void qs(int left,int right)
{
    if(left>=right)
        return;
    int i=left,j=right;
    a[0]=a;
    while(i<j)
    {
        while(i<j&&a[j].s>=a[0].s)
            j--;
        if(i<j)
            a=a[j];
        while(i<j&&a.s<=a[0].s)
            i++;
        if(i<j)
            a[j]=a;
    }
    a=a[0];
    qs(left,i-1);
    qs(i+1,right);
}
int main()
{
    int n,m,i,p,q,flag=0;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {   
        cin>>p>>q;
        if(p>q)
        {   
            a.s=q;
            a.e=p;
        }
        else
        {
            a.e=q;
            a.s=p;
        }
    }
    qs(1,m);
    int max1=0,sum=0,num=1;

    for(i=1;i<=m;i++)
    {
        if(a.s<=num)
        {
            if(max1<a.e)
            {
                max1=a.e;
            }

        }
        else
        {
            if(max1==0)
            {
                flag=1;
                break;

            }
            sum++;
            num=max1+1;
            max1=0;
        }

        if(num>n)
            break;

    }

    if(i==m+1)
    {
        if(a[m].e==n)
        {
            sum++;
        }
        else
            flag=1;
        if(a[m].s>num)
            flag=1;
    }

    cout<<endl;
    if(flag==0)
    cout<<sum<<endl;
    else
    cout<<"No";
    getchar();
    getchar();
    return 0;
}

/*
6 7
5 6
3 4
1 3
1 2
2 4
3 5
2 3
*/[/code]

Why should we hire you? I think you know better then me sir.  xboter 2014