[BZOJ3389]&&[Usaco2004 Dec]Cleaning Shifts 安排值班

2014-09-20
竞赛题解 / 贪心
BZOJUSACO

描述 Description

一天有 T(1≤T≤10^6) 个时段．约翰正打算安排他的 N(1≤N≤25000) 只奶牛来值班，打扫牛棚卫生．每只奶牛都有自己的空闲时间段 Si，Ei，只能把空闲的奶牛安排出来值班．而且，每个时间段必需有奶牛在值班．那么，最少需要动用多少奶牛参与值班呢？如果没有办法安排出合理的方案，就输出 - 1.

输入格式 InputFormat

第 1 行：N，T．

第 2 到 N+1 行：Si，Ei．

输出格式 OutputFormat

最少安排的奶牛数．

样例输入 SampleInput

3 10
1 3
5 7
8 10

样例输出 SampleOutput

-1

来源 Source

Silver

BZOJ 3389

代码 Code

按左端点排序后每次取能取到的且右端点最大的牛。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
pair <int,int> a[25005];
inline void read(int &x)
{
    x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
int ans;
int main()
{
    read(n);read(t);
    a[0]=make_pair(0,0);
    for (i=1;i<=n;i++) read(a[i].first),read(a[i].second);
    sort(a+1,a+n+1);
    ans=0;x=0;
    while (a[x].second<t)
    {
        y=0;
        for (i=x+1;a[i].first<=a[x].second+1;i++) if (a[y].second<a[i].second) y=i;
        if (y==0)
        {
            printf("%d\n",-1);
            return 0;
        }
        x=y;
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}