經(jīng)典的貪心問題，和分組問題很像。不過這里我們還得維護(hù)坐標(biāo)信息。

#include<bits/stdc++.h> using namespace std; #define x first #define y second; const int N=1e5+10; typedef pair<int,int> PII; struct node{int l,r,id;}; bool cmp(node a,node b) {if(a.l!=a.l) return a.r<b.r;return a.l<b.l; } vector<node>ve; int n,ans[N]; int main(void) {cin>>n;for(int i=1;i<=n;i++){int l,r; cin>>l>>r;ve.push_back({l,r,i});}sort(ve.begin(),ve.end(),cmp);priority_queue<PII,vector<PII>,greater<PII> >q;//小根堆 存每組最后一個數(shù)for(int i=0;i<n;i++){int l=ve[i].l,r=ve[i].r;if(!q.size()) q.push({r,q.size()+1}),ans[ve[i].id]=q.size();else{auto temp=q.top();int x=temp.x,id=temp.y;if(x<l) {q.pop();q.push({r,id});ans[ve[i].id]=id;}else{q.push({r,q.size()+1});ans[ve[i].id]=q.size();}}}cout<<q.size()<<endl;for(int i=1;i<=n;i++) cout<<ans[i]<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的111. 畜栏预定【贪心】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。