预定会议室

来自计算思维百科
跳转至: 导航搜索
预定会议室1.jpg

某公司只有1间会议室,但有5个团队申请使用。各团队申请使用会议室的时间表如下图所示。会议室只能让一个团队使用,所以只能挑选出不重叠的会议。那么最多能选出几个呢?

预定会议室2.png

解决方案

方案一-蛮力法

此题具有多种答案,互相不重叠的会议集合都是答案,所要求出的最优解就是这些集合中的最大的一个。用蛮力法解决就是找出所有的可能性,并在其中找出不重叠的最大集合。下面是集合中的三种解(黄色的会议是解),相比较而言,第二种解和第三种解的会议数更多。

预定会议室3.png

预定会议室4.png

运用的计算思维

方案一中,将所有可能的解空间列出,再在解空间中搜索会议数最多的解,是一种机械化的思维方式。

方案二-贪心法

贪心法在每个阶段能够找到当前最优解,而当前最优解的找法也不同。就拿本题来说,有两种方式来找最优解。

第一种,将从开会时间最短的会议开始逐个检索,并找出不与前面的会议发生冲突的会议。

各个会议的开会时间表以及冲突表如下所示,有冲突的会议用1表示:

会议

时间

时长

1

6:00~7:00

1小时

2

1:00~5:00

4小时

3

4:30~6:00

1小时半

4

1:00~4:00

3小时

5

4:00~6:00

2小时

 

会议

1

2

3

4

5

1

0

0

0

0

0

2

0

0

1

1

1

3

0

1

0

0

1

4

0

1

0

0

0

5

0

1

1

0

0

将会议的时长按从小到大排序为:

会议1 < 会议3 < 会议5 < 会议4 < 会议2

第一步:选中会议1,查找冲突表,没有会议与之冲突;

第二步:选中会议3,查找冲突表,会议2和会议5与之冲突;

第三步:选中会议4,结束。

于是,选中的会议为1、3、4。

预定会议室5.png

这种贪心方式会优先选择会议时长短的,所以会忽略1、4、5这种解答。

所以就出现了第二种贪心法,从最早结束的会议开始选择。选择最早结束的会议后,删除与这个会议发生冲突的会议,然后再从中选择最早结束的会议直到找到解答。

会议

结束时间

1

7:00

2

5:00

3

6:00

4

4:00

5

6:00

根据上表,可以得出会议结束时间从早到晚排序如下:

会议4 < 会议2 < 会议3 = 会议5 < 会议1

第一步:选择会议4,查找冲突表,排除会议2;

第二步:选择会议3,查找冲突表,排除会议5;

第三步:选择会议1,结束。

这时,我们可以得到解为会议1、3、4,而这种解使得会议室利用率达到最大。

预定会议室6.png

运用的计算思维

贪心法面在每一步面对多种选择,都会找出当前最优解,运用了优化的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015