21-问题分析

2.4.1　问题分析

这是一个典型的会议安排问题，会议安排的目的是能在有限的时间内召开更多的会议（任何两个会议不能同时进行）。在会议安排中，每个会议i都有起始时间b_i和结束时间e_i，且b_i<e_i，即一个会议进行的时间为半开区间[b_i，e_i）。如果[b_i，e_i）与[b_j，e_j）均在“有限的时间内”，且不相交，则称会议i与会议j相容的。也就是说，当b_ie_j或b_je_i时，会议i与会议j相容。会议安排问题要求在所给的会议集合中选出最大的相容活动子集，即尽可能在有限的时间内召开更多的会议。

在这个问题中，“有限的时间内（这段时间应该是连续的）”是其中的一个限制条件，也应该是有一个起始时间和一个结束时间（简单化，起始时间可以是会议最早开始的时间，结束时间可以是会议最晚结束的时间），任务就是实现召开更多的满足在这个“有限的时间内”等待安排的会议，会议时间表如表2-6所示。

| 会议i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | :----- | | 开始时间b_i | 8 | 9 | 10 | 11 | 13 | 14 | 15 | 17 | 18 | 16 | | 结束时间e_i | 10 | 11 | 15 | 14 | 16 | 17 | 17 | 18 | 20 | 19 |

会议安排的时间段如图2-7所示。

从图2-7中可以看出，{会议1，会议4，会议6，会议8，会议9}，{会议2，会议4，会议7，会议8，会议9}都是能安排最多的会议集合。

要让会议数最多，我们需要选择最多的不相交时间段。我们可以尝试贪心策略：

（1）每次从剩下未安排的会议中选择会议 具有最早开始时间且与已安排的会议相容 的会议安排，以增大时间资源的利用率。

（2）每次从剩下未安排的会议中选择 持续时间最短且与已安排的会议相容 的会议安排，这样可以安排更多一些的会议。

（3）每次从剩下未安排的会议中选择 具有最早结束时间且与已安排的会议相容 的会议安排，这样可以尽快安排下一个会议。

思考一下，如果选择最早开始时间，则如果会议持续时间很长，例如8点开始，却要持续12个小时，这样一天就只能安排一个会议；如果选择持续时间最短，则可能开始时间很晚，例如19点开始，20点结束，这样也只能安排一个会议，所以我们最好选择那些开始时间要早，而且持续时间短的会议，即最早开始时间+持续时间最短，就是 最早结束 时间。

因此采用第（3）种 贪心策略，每次从剩下的会议中选择具有最早结束时间且与已安排的会议相容的会议安排 。