题意：输入n，n行每行两个数分别为起始时间和终止时间，一台机器在一个时间段只能完成一项工作，
求完成n项工作至少需要几台机器。
第一种解法：优先队列将起始时间从小到大排列，将起始最早的结束时间压入队列，如果它小于下一个的起始时间，出队，下一个结束时间入队
否则下一个结束时间直击入队，结束，统计队列中元素个数即可。
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int maxn=1e6+100; priority_queue<int,vector<int>,greater<int> >q;//从大到小的优先队列 pair<int,int>x[maxn]; int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d%d",&x[i].first,&x[i].second); } sort(x,x+n+1);//先按开始时间排序，开始相等按结束排序 q.push(0); for(int i=1;i<=n;i++) { if(q.top()<=x[i].first) { q.pop(); q.push(x[i].second); } else q.push(x[i].second); } cout<<q.size()<<endl; } }
第二种解法 由于数据较大，但点的个数有限，需将各点离散化，去重，标记左右端点类比前缀和求解。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; #define maxn 200005 typedef pair<int,int>P; P a[maxn]; vector<P>vec; int temp[maxn]; int n; int main() { while(scanf("%d",&n)!=EOF) { int len=0; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].first,&a[i].second); temp[len++]=a[i].first;//离散化 temp[len++]=a[i].second;//temp数组保存的只有输入的 左右端点 } sort(temp,temp+len);//排序 len=unique(temp,temp+len)-temp;//去重 for(int i=1;i<=n;i++) { int x=lower_bound(temp,temp+len,a[i].first)-temp;//查找左右端点 在temp数组中的位置 int y=lower_bound(temp,temp+len,a[i].second)-temp;//x,y 返回下标 // cout<<x<<" "<<y<<" "<<temp[x]<<" "<<temp[y]<<endl; vec.push_back(P(x,1));//标记端点 左or右 vec.push_back(P(y,-1)); } sort(vec.begin(),vec.end());//按端点大小排序 //cout<<vec.size()<<endl; int ans=0,cnt=0; //类比前缀和 for(int i=0;i<vec.size();i++) { if(vec[i].second==1)//左端点 { ans++; //cout<<temp[vec[i].first]<<" "<<ans<<endl; cnt=max(ans,cnt); } else ans--; } cout<<cnt<<endl; } return 0; }