Description

Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.

Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.

Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.

Input

• Line 1: Two space-separated integers: N and T

• Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.

Output

• Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.
  Sample Input
  3 10
  1 7
  3 6
  6 10
  Sample Output
  2

Hint

This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.

INPUT DETAILS:

There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.

OUTPUT DETAILS:

By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.

理解：

??給定一個時間T和N個時間區(qū)間，求最少需要多少個區(qū)間覆蓋總區(qū)間[1,T]，無法覆蓋區(qū)域[1,T]時輸出-1。
類似于工作排序問題：
貪心策略：在符合時間情況的選項中 選擇結(jié)束時間最遲的牛
具體步驟：按照開始時間升序排列 ，如果開始時間相同，按照結(jié)束時間升序排列設(shè)t為最終結(jié)束時間。兩層循環(huán)嵌套第一層是尋找每一個時間段開始工作的牛，第二層是尋找在同一時間段開始工作的牛中的最晚結(jié)束的牛。如果外層循環(huán)有一個點沒有找到，則退出循環(huán)返回-1；

題解：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int x,y;
    bool operator<(node t)const    //重載<運算符 
    {
        return x<t.x;
    }
} a[25000];
int n,T;
int main()
{
    scanf("%d%d",&n,&T);
    for(int i=0; i<n; i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a,a+n);            //開始時刻升序排列 
    if(a[0].x>1)       //沒有牛在第一個時段打掃 
    {
        puts("-1");
        return 0;
    }
    int p=0,ans=0;               
    for(int i=0; i<n;)
        if(a[i].x <= p+1)     //如果第i個牛從第p+1段之前開始打掃 
        {
            int mx = -1;
            while(i<n && a[i].x<=p+1)
            {
                mx = max(mx,a[i].y);
                i++; 
            }
            ans++         //挑選這頭牛 
            p = mx;         //把p重置為這頭牛最后完成的時間段，p已完成，p+1未完成 
            if(p>=T) break;//這個語句也是很關(guān)鍵的
        }
        else break;  
    if(p<T) puts("-1");
    else printf("%d\n",ans);
    return 0;
}