首页 > 代码库 > bzoj 3389: [Usaco2004 Dec]Cleaning Shifts安排值班 -- 贪心

bzoj 3389: [Usaco2004 Dec]Cleaning Shifts安排值班 -- 贪心

2024-09-24 23:49:39   216人阅读

3389: [Usaco2004 Dec]Cleaning Shifts安排值班

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

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

Input

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

Output

 
    最少安排的奶牛数．

Sample Input


3 10
1 7
3 6
6 10

Sample Output


2


样例说明
奶牛1和奶牛3参与值班即可．

HINT

排序后贪心

 

#include<map>#include<cmath>#include<queue>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define N 25010struct qaz{int l,r;}a[N];bool cmp(qaz a, qaz b){return a.l==b.l?a.r<b.r:a.l<b.l;}int n,T,now,cnt,tmp,ans;int main(){    scanf("%d%d",&n,&T);    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);    sort(a+1,a+n+1,cmp);    while(now<T)    {        tmp=now;        while(cnt<n&&a[cnt+1].l<=tmp+1){cnt++;now=max(now,a[cnt].r);}        if((cnt==n&&a[cnt].r<T)||(a[cnt+1].l>now+1)){puts("-1");return 0;}        ans++;    }    now<T?puts("-1"):printf("%d\n",ans);}

 

bzoj 3389: [Usaco2004 Dec]Cleaning Shifts安排值班 -- 贪心


联系
我们