题意:给出n头牛必须单独占用一台机器的时间段,问至少需要多少台机器
先按照每头牛的时间的x来排序,然后用一个优先队列(优先选取最小的)维护已经喂好的牛的最小的结束时间
比如现在优先队列里面有m头牛已经完成了饲喂,
对于第m+1头牛, 如果它的开始时间小于这m头牛里面的最小的结束时间,那么必须增加一台机器,同时把第m+1头牛放进队列
如果它的开始时间大于这m头牛里面的最小的结束时间,把当前队头弹出,再把m+1头牛放进去
#include<iostream> #include<cstdio> #include<cstring> #include <cmath> #include<stack> #include<vector> #include<map> #include<set> #include<queue> #include<algorithm> using namespace std; typedef long long LL; const int INF = (1<<30)-1; const int mod=1000000007; const int maxn=1000005; struct node{ int x,y,id; bool operator < (const node &rsh) const { return rsh.y < y; } } a[maxn]; int cmp(node n1,node n2){ return n1.x < n2.x; } int ans[maxn]; int n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d %d",&a[i].x,&a[i].y); a[i].id=i; } sort(a+1,a+n+1,cmp); priority_queue<node> q; q.push(a[1]); ans[a[1].id]=1; int cnt=1; for(int i=2;i<=n;i++){ node tmp=q.top(); if(a[i].x <= tmp.y){ ans[a[i].id]=++cnt; q.push(a[i]); } else{ q.pop(); q.push(a[i]); ans[a[i].id] = ans[tmp.id]; } } printf("%d ",cnt); for(int i=1;i <= n;i++) printf("%d ",ans[i]); return 0; }