7-2 会场安排问题 (20分)

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。）

输入格式:

第一行有 1 个正整数k，表示有 k个待安排的活动。接下来的 k行中，每行有 2个正整数，分别表示 k个待安排的活动开始时间和结束时间。时间以 0 点开始的分钟计。

输出格式:

输出最少会场数。

输入样例:

输出样例:

算法：

错误解法：

按照结束时间排序，然后开始放活动，这样贪心可以使每次放的活动最多。

这样做是错的，这样只能保证第一次放的活动是最多的，但是具备有后效性，不能使全局最优。网上的很多解法都是这个，是错误的。

比如数据：

6
90 98---1
8 32----2
18 48---3
16 82---4
83 84---5
39 89---6

这组数据的答案是3，我们把活动按照1-n编号，那么分别用三个会场装（2， 6）、（4， 5）、（3， 1），就能完成任务，答案是3。

但是如果按照贪心排结束时间的做法，答案是4，在第一次拿的时候我们拿了很多，3个，但是这也导致后面的活动都不得不单独开一个会场，导致答案为4，不是最优解。这也就是典型的局部最优不能带来全局最优。

附上错误代码：

#include <iostream>
using namespace std;

typedef struct 
{
    int start;
    int end;
}Event;


int main(){
    int k;                                   //表示有 k个待安排的活动
    cin>>k;
    Event event[k+1];
    for(int i=1;i<=k;i++){
        cin>>event[i].start>>event[i].end;   //活动开始时间和结束时间
    }
    
    for(int i=1;i<=k;i++){                  //event数组按活动的结束时间从小到大排序 
        int min=event[i].end,min_id=i;      //冒泡 
        for(int j=i+1;j<=k;j++){   
            if(event[j].end<min) {
                min = event[j].end;
                min_id = j;
            }
        }
        swap(event[i],event[min_id]);
    }
    
    int room[k+1]={0};                    // 会场，room[i]记录活动结束的时间，即表示第i个会场开始空闲的时间 
                                          // 初始化为0，表示未使用，若不是0则代表该会场已经被使用过 
    for(int i=1;i<=k;i++){
        for(int j=1;j<=k;j++){
            if(room[j]<=event[i].start) 
            {
                room[j]=event[i].end;
                break;
            }
        }    
    }

    int count=0;                          //统计room数组非0单元个数，即最小使用数 
    for(int i=1;i<=k;i++){    
        if(room[i]==0) break;
        count++;
    }
    
    cout<<count<<endl;
}

稍微改一下就好

正确代码：

#include <iostream>
using namespace std;

typedef struct 
{
    int start;
    int end;
}Event;


int main(){
    int k;                                   //表示有 k个待安排的活动
    cin>>k;
    Event event[k+1];
    for(int i=1;i<=k;i++){
        cin>>event[i].start>>event[i].end;   //活动开始时间和结束时间
    }
    
    for(int i=1;i<=k;i++){                  //event数组按活动的开始时间从小到大排序 
        int min=event[i].start,min_id=i;    //冒泡 
        for(int j=i+1;j<=k;j++){   
            if(event[j].start<min) {
                min = event[j].start;
                min_id = j;
            }
        }
        swap(event[i],event[min_id]);
    }
    
    int room[k+1]={0};                    // 会场，room[i]记录活动结束的时间，即表示第i个会场开始空闲的时间 
                                          // 初始化为0，表示未使用，若不是0则代表该会场已经被使用过 
    for(int i=1;i<=k;i++){
        for(int j=1;j<=k;j++){
            if(room[j]<=event[i].start) 
            {
                room[j]=event[i].end;
                break;
            }
        }    
    }

    int count=0;                          //统计room数组非0单元个数，即最小使用数 
    for(int i=1;i<=k;i++){    
        if(room[i]==0) break;
        count++;
    }
    
    cout<<count<<endl;
}

下图重叠的地方表示活动之间不兼容，即不能在同一会场进行

最大重叠数 = 最小会场数