6.3 会场安排问题

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

输入格式:

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

输出格式:

输出最少会场数。

输入样例1:

5
1 23
12 28
25 35
27 80
36 50

输出样例1:

3

输入样例2:

14
34 99
53 57
19 75
11 95
50 76
33 76
61 74
22 69
16 28
7 44
23 92
14 65
7 19
36 52

输出样例2:

9

输入样例3:

57
71 73
23 41
1 78
39 74
6 76
31 63
0 74
64 82
15 46
65 69
5 19
64 71
15 71
23 29
10 42
4 77
15 16
29 52
50 71
60 63
32 87
16 47
50 61
42 94
1 29
86 91
9 22
10 71
31 87
13 88
44 49
7 43
62 96
20 71
6 57
22 24
68 92
66 94
32 83
18 77
79 97
53 83
6 8
31 81
42 98
72 90
27 42
13 64
33 93
2 34
17 29
29 70
18 88
7 54
11 23
3 46
30 89

输出样例3:

30

算法思想1：

排序规则：先按开始时间非递减排序，开始时间相同时按结束时间非递减排序。
原序：0 1 2 3 4 5 6 7
现序：1 3 2 5 4 6 7 8（为了方便理解，这里从1开始）
会场安排：排序后，按顺序遍历各活动，各活动再遍历已安排活动的会场。将活动安排到满足时间条件的会场，没有满足时间条件的会场，则占用新的会场。
图片说明
会场排序：之前被占用的会场，根据会场最近一次活动的结束时间非递增排序。
图片说明
会场排序：之前被占用的会场，根据会场最近一次活动的结束时间非递增排序。
图片说明
会场排序：之前被占用的会场，根据会场最近一次活动的结束时间非递增排序。
图片说明
会场排序：之前被占用的会场，根据会场最近一次活动的结束时间非递增排序。
图片说明
会场排序：之前被占用的会场，根据会场最近一次活动的结束时间非递增排序。
图片说明
会场排序：之前被占用的会场，根据会场最近一次活动的结束时间非递增排序。
图片说明
会场排序：之前被占用的会场，根据会场最近一次活动的结束时间非递增排序。
图片说明
最终安排：
1 → 5；
2 → 3 → 8；
4；
6 → 7；

参考代码1：

#include<iostream>
#include<algorithm>
#define LEN 10001

using namespace std;

struct Activity{
    int begin;//开始时间 
    int end;//结束时间
}activity[LEN];

bool cmp(Activity a,Activity b){
    if(a.end!=b.end) 
        return a.end<b.end;
        //优先进行最先结束的活动 
    else 
        return a.begin<b.begin;
        //当结束时间相同时,优先进行最早开始的活动
}

bool decmp(int a,int b){//递减 
    return a>b;
}

int main(){

    int num;//待安排活动数 
    cin >> num;

    for(int i=0;i<num;i++)
        cin >> activity[i].begin >> activity[i].end;

    sort(activity,activity+num,cmp);//对活动进行排序 

    int count=1;//占用会场数 
    int nextEnd[LEN];//存放会场i上一活动的结束时间 

    nextEnd[1]=activity[0].end;//结束时间最早的活动最先安排 

    for(int i=1;i<num;i++){//从第二个待安排的活动开始安排会场 
        int flag=0;
        for(int j=1;j<=count;j++){//遍历已经占用的会场 
            if(activity[i].begin>=nextEnd[j]){//满足条件 
                flag=1;
                nextEnd[j]=activity[i].end;//更新当前会场的结束时间 
                sort(nextEnd+1,nextEnd+num,decmp); 
                //每次更新后,对已占用的会场,按结束时间非递增排序，
                //最先结束的可以容纳开始时间更早的活动,以达到最优解
                break;
            }
        }
        if(!flag){//已占用的会场中没有可供使用的 
            count++;//使用新会场 
            nextEnd[count]=activity[i].end;
            sort(nextEnd+1,nextEnd+num,decmp);
        }
    }

    cout << count <<endl; 

    return 0;
}

算法思想2：

排序规则：先按开始时间非递减排序，开始时间相同时按结束时间非递减排序。
原序：0 1 2 3 4 5 6 7
现序：1 3 2 5 4 6 7 8（为了方便理解，这里从1开始）
会场安排：排序后，按顺序遍历各活动。若当前活动没被安排，后面还有没被安排并满足时间条件的活动，则将这些活动安排在同一个会场。
图片说明
最终安排：
1 → 4 → 8；
2；
3 → 5 → 7；
6；

参考代码2：

#include<iostream>
#include<algorithm>
#define LEN 10001

using namespace std;

struct Activity{
    int begin; 
    int end;
    int flag;//标记该活动是否被安排，0表示未安排，1表示已安排
}activity[LEN];

bool cmp(Activity a,Activity b){
    if(a.begin!=b.begin) 
        return a.begin<b.begin;
        //优先进行最先开始的活动 
    else 
        return a.end<b.end;
        //当开始时间相同时,优先进行最早结束的活动
}

int main(){

    int num;
    cin>>num;

    for(int i=0;i<num;i++){
        cin >> activity[i].begin >> activity[i].end;
        activity[i].flag=0;
    }

    sort(activity,activity+num,cmp);

    int count=0; 

    for(int i=0;i<num;i++){//遍历每个活动 
        if(!activity[i].flag){//活动i还没有被安排会场 
            int temp=i;//temp暂存该会场目前已经进行的最后一项活动的序号 
            for(int j=i+1;j<num;j++){//遍历活动i的后续活动 
                if(!activity[j].flag&&activity[j].begin>=activity[temp].end){
                    //如果活动j还没有被安排会场,而且开始时间大于活动i的结束时间 
                    temp=j;//更新该会场最近一次活动的序号 
                    activity[j].flag=1; 
                }
            }
            count++;//一次大循环,符合条件的活动都被安排到一个会场
        }
    }

    cout <<count <<endl;

    return 0;
}