本文共 1443 字，大约阅读时间需要 4 分钟。
第一行一个正整数n (n <= 10000)代表活动的个数。第二行到第(n + 1)行包含n个开始时间和结束时间。开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000
我们想像一下k增加1的过程： 因为我们是按照开始时间排序的，意味着当前考虑的这个活动开始的时候，k个教室里都有活动没结束（因为如果有一个教室的活动结束了，我们就可以安排这个活动进入那个教室而不冲突，从而不用增加k)。这就意味着在这个活动开始的时间点，算上目前考虑的这个活动，有(k + 1)个活动正在进行，同一时刻有(k + 1)个活动在进行，无论我们如何安排教室，都至少需要(k + 1)个教室。因为每个教室里不能同时进行两个活动。而我们的策略恰好需要(k + 1)个教室，所以是最优的。
这个策略也告诉我们，如果从时间轴上“宏观”考虑这个问题。考虑每个时间点同时进行的活动个数，作为这个时间点的厚度（把活动开始和结束时间想像成线段，那么每个时间点有多少条线段覆盖它，可以简单理解为“厚度”），我们至少需要最大厚度那么多个教室——因为那时恰好有最大厚度那么多个活动同时进行，而我们这个贪心策略恰好给了我们一个用最大厚度那么多个教室安排全部活动的一个方案。
如果只需要教室的个数，我们可以把所有开始时间和结束时间排序，遇到开始时间就把厚度加1，遇到结束时间就把厚度减1，显然最初始和最后结束时的厚度是0，在一系列厚度变化的过程中，峰值（最大值）就是最多同时进行的活动数，也是我们至少需要的教室数。
#include #include #include #include #include #include #include using namespace std;struct Node{ int s,e; bool operator < (const Node o)const{ return s < o.s; }};int n;struct Node nodes[10000+5];priority_queue ,greater > pq; //保存结束时间int main() { ios::sync_with_stdio(false); cin >> n; for(int i = 0; i < n; ++i){ cin >> nodes[i].s >> nodes[i].e; } sort(nodes,nodes+n); int ans = 0; for(int i = 0; i < n; ++i){ if(!pq.empty()){ int e = pq.top(); if(nodes[i].s >= e){//如果开始时间大于某个结束时间，说明不需要新的教室 pq.pop();//把这个结束的取出来，此说该教室结束时间要更新 pq.push(nodes[i].e);//更新该教室的结束时间 } else{//如果 此时没有结束的 ++ans; pq.push(nodes[i].e); } } else{//处理第一个 ++ans; pq.push(nodes[i].e); } } cout << ans; return 0; }
转载地址：http://dhimi.baihongyu.com/