首先按照开始时间从小到大排序.
其实只要维护一个结束时间的最小堆,每次比较开始时间和堆中最小时间的大小,如果比它大就放入堆中并且时间就要变成当前任务的结束时间,
否则就要新开一个教室.并且把结束时间加入堆中,注意判断堆是否为空.
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; struct point { int x,y; bool operator < (const point a) const { return x<a.x; } }p[10001]; int main() { int n; priority_queue<int,vector<int>,greater<int> >que; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y); sort(p,p+n); //for(int i=0;i<n;i++) printf("%d %d\n",p[i].x,p[i].y); que.push(p[0].y); int ans=1; for(int i=1;i<n;i++) { if(!que.empty()) { int a=que.top(); //printf("%d\n",p[i].x); if(p[i].x>=a) { que.pop(); a=p[i].y; que.push(a); } else { ans++; que.push(p[i].y); } } else { ans++; que.push(p[i].y); } } printf("%d\n",ans); return 0; }