会场安排问题
【问题描述】
假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点有不同颜色的最小着色数，相应于要找的最小会场数。）
【数据输入】
第一行有1个正整数k，表示有k个待安排的活动。接下来的k行中，每行有两个正整数，分别表示k个待安排的活动开始时间和活动结束时间。时间以0点开始的分钟计。
【分析与解答】
设所给的n个活动1，2，....，n，它们的的开始时间和结束时间分别为s[i]和f[i]，i=1~n，且f[1]<f[2]<.....<f[n]。
（1）容易想到用算法GreedySelector（活动安排问题）来安排会场。在最坏情况下算法需要O（n2）计算时间。
（2）实际上，可以设计出一个更有效的算法。将n个活动1，2，....，n看做实直线上的n个半闭活动区间[s[i]，f[i]]，i=1~n。所讨论的问题实际上是求这n个半闭区间的最大重叠数。因为重叠的活动区间所相应的活动是互不相容的。若这n个活动区间的最大重叠数为m，则这m个重叠区间所对应的活动互不相容，因此至少要安排m个会场来容纳这m个活动。
为了有效地对这n个活动进行安排，首先将n个活动区间的2n个端点排序。然后，用扫描算法，从左到右扫描整个直线。在每个事件点处（即活动的开始时刻或结束时刻）作会场安排。当遇到一个开始时刻s[i]，就将活动i安排在一个空闲的会场中。遇到一个结束时刻f[i]，就将活动i占用的会场释放到空闲会场栈中，已备使用。经过这样一遍扫描后，最多安排了m个会场（m是最大重叠区间数）。因此所作的会场安排是最优的。上述算法所需的计算时间主要用于对2n个区间端点的排序，这需要O（nlogn）计算时间。
#include <iostream>#include <vector>#include <algorithm>using namespace std;typedef struct node{int data;//时间值int flag;//1表示开始时间，0表示结束时间}Node;bool compare(Node n1, Node n2){return n1.data<n2.data;//升序排列}int maxrepeat(vector<Node> v)//最大重叠数{int curr=0, sum=0;vector<Node>::iterator it=v.begin();for(; it<=v.end(); it++){ if((*it).flag) { curr++; if(curr>sum) sum=curr; } else curr--;}return sum;}void main(){int i, n;vector<Node> v;cin>>n;Node t;for(i=1;i<=2*n; i++){cin>>t.data;t.flag=i%2;v.push_back(t);}sort(v.begin(),v.end(),compare);cout<<maxrepeat(v)<<endl;}