Cleaning Shifts POJ - 2376 (经典区间贪心)

题目：

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

翻译：农场主约翰指派他的一些牛（1<=n<=25000）在谷仓周围做一些清洁工作。他总是希望有一头牛来清理东西，并把一天分成T班（1<=T<=1000000），第一班是1班，最后一班是T班。每头奶牛只能在白天的某个时间间隔内用于清洁工作。任何被选为清洁工作的奶牛都将在其整个时间间隔内工作。你的工作是帮助农夫约翰安排一些奶牛轮班，以便（i）每个轮班至少分配一头奶牛，以及（ii）尽可能少的奶牛参与清洁。如果无法为每个班次分配一头奶牛，请打印-1。

先输入两个数n，t,第二行到结尾输出不同段的班次到班次。

这是一道区间覆盖的问题，要求的是让几头牛的班次可以覆盖掉一天的班次。

让我们先想一个问题，有那么些固定的小线段(可能交错，可能分离)，选择其中一些,让它们都覆盖整个大线段(目标线段)。如果是这样，我们会怎么选择。 第一印象，我们会先把长的选出来，再仔细去思考，我们会把小线段的左端按着相对于大线段的顺序从左往右排好，在右端相同的时候，我们把左端也按着从左往右排号 这样先选择第一条线段可以到达的最右端作为贪心的right，在第一条线段之后，去贪心那条左端小于等于right且右端最右的一条线段，等到最左大于right把right更新为之前最右的那个点，按着这个的贪心思路去铺满整个大线段。具体就看代码啦：

#include<iostream>
#include<algorithm>

using namespace std;

struct node{
    int l,r;//左右端点 
}p[25005]; 

bool cmp(node a,node b){
    if(a.l==b.l)
    return a.r>b.r;
    return a.l<b.l;
}//给sort排序定好顺序，按着左端优先按着从左到右的顺序排列，在左端一样的条件下，右端最右的先排

int main()
{
    int n,m;
    cin>>n>>m;
    int x=0,y=0;
    for(int i=0;i<n;i++){
        cin>>p[i].l>>p[i].r;
        if(p[i].l==1)x=1;
        if(p[i].r==m)y=1;
    }
    if(x==0||y==0){//没有存在这个点的时候，就
        cout<<-1<<endl;
        return 0;
    }

    sort(p,p+n,cmp);
    int right=p[0].r;//表示当前线段最右的一个点
    int z=right;//z表示贪心后最右的点 
    int ans=1;
    for(int i=1;i<n;i++){
        if(p[i].l>right+1){            
                ans++;
                right=z;
        }
        if(p[i].l<=right+1){//注意这里是right+1，为什么要这样？这个放在结尾说
            z=max(z,p[i].r);
            if(p[i].r==m){
                right=m;
                ans++;break;
            }
        }
    }
    if(right>=m)
    cout<<ans;
    else cout<<-1<<endl;
}

在贪心的过程中，线段的左右节点比较的是right+1，而不是right。假如我们比较的是right的话，就没有办法将right+1（这个时候已经是下一个线段的左端了)这种情况（情况1可能需要）的右端列进最右的点。也就是说，z所更新的那个点要包括下一条线段的最右端，这样子线段才可以无缝的链接起来。具体看看下面图片