本文共 2153 字，大约阅读时间需要 7 分钟。

区间划分问题Interval Partitioning

问题描述：

       Lecture j starts at sj and finishes at fj

       Goal：find minimum number of classrooms to schedule all lectures so that no two occur at the same time in the same room.

       下面给出一个例子?：

❗算法描述❗：

       定义 depth 为 在一段时间内，需要的最多教室数。

       （Def：The depth of a set of intervals is the maximum number that pass over and single point on the time-line.）

       如：在上面所举的例子中，depth = 3。

       按讲座的开始时间，对讲座进行排序。从开始时间最早的讲座开始遍历，如果下一个讲座与当前讲座兼容，继续；如果不兼容，另外开辟一个教室。

       伪代码如下：

Sort intervals by starting time so that s[1] ≤ s[2] ≤ ... ≤ s[n] .d = 1    //number of allocated classroomsfor j = 1 to n    if (lecture j is compatible with some classroom k)        schedule lecture j in classroom k    else        allocate a new classroom d + 1        schedule lecture j in classroom d + 1        d = d + 1

       实现该算法，复杂度为O(n * log n)。

       ① 对于每一个教室 k ，要记录在该教室进行的最后一个讲座的结束时间，以确定下一个讲座是否可以在该教室中举办；

       ② 当开辟新教室后，再对下一个讲座进行兼容性检查时，就需要与depth个教室进行比较，选择兼容性最好的教室。所以，开辟新教室时，应该把该教室的使用结束时间也加入到一个队列中；对一个教室进行再次添加讲座时，也应该把该教室的使用结束时间更新！

       在该算法中，会用到  a priority queue，优先队列要用到堆结构实现。但我们可以使用C++标准库。（上学期数据结构学的“堆”也要复习了！）

代码✍：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;struct LECTURE{	double start;	double finish;};bool comp(const LECTURE &a, const LECTURE &b);//定义比较结构struct cmp{	bool operator ()(double &a, double &b)	{		return a > b;//最小值优先	}};int main(){	int num;	cout << "请输入讲座的数目:" << endl;	cin >> num;	vector
       
         lectures(num);	cout << "请依次输入讲座的开始时间、结束时间:" << endl;	for (int i = 0; i < num; ++i)	{		cin >> lectures[i].start >> lectures[i].finish;	}	//按讲座开始时间对讲座进行排序	sort(lectures.begin(), lectures.end(), comp);	priority_queue
        
         , cmp> classrooms; //记录教室的使用结束时间，最小级优先 classrooms.push(0); //初始化一个教室 for (int i = 0; i < num; ++i) { //如果讲座的开始时间早于教室的最早使用结束时间，开辟一个新教室 if (lectures[i].start < classrooms.top()) { classrooms.push(lectures[i].finish); //将新教室的使用结束时间保存 } else { //将教室的最早结束时间替换成该讲座的结束时间 classrooms.pop(); classrooms.push(lectures[i].finish); } } cout << "需要教室的最大数目:" << endl; cout << classrooms.size() << endl; return 0;}bool comp(const LECTURE &a, const LECTURE &b){ return a.start < b.start;}
        
       
      
     
    
   

测试：

转载地址：http://uxtai.baihongyu.com/