教室调度问题—贪婪算法—要求尽可能多的将课程安排在某间教室，如何安排？——结束时间最早的课,动态规划——背包问题——贪心算法

问题描述

要求尽可能多的将课程安排在某间教室，如何安排？

处理思路

我们没有办法将这些课都安排在一间教室，因为有些课的上课时间有冲突。

具体做法如下:

1）选出结束时间最早的课，它就是要在这间教室上的第一堂课

2）接下来，必须选择第一堂课结束后才开始的课。同样，要选择结束最早的课，这是在这间教室上的第二堂课。

3）重复以上的步骤，即可完成排课

实现过程

1） 美术课结束时间最早

2）美术课结束后，接下来的课必须在10:00后开始，所以英语课不满足条件。

数学课满足

3）数学课结束后，按照之前的处理方法，选择音乐课

因为这间教室的排课表为：

很多人会说，这个算法太容易，太显而易见，肯定不对。但这正是贪婪算法的优点——简单易行！

贪婪算法的思想：每一步都采取最优的做法。比如上例中，每次都选择结束最早的课，所以用专业术语说就是：每一步都选取局部最优解，最终得到的就是全局最优解。

再比如现实生活中，找67元的零钱。没有人会首先想到从抽屉里找67个1元钱给顾客，为什么？因为这会产生67次的找钱行为，我们都希望用最少的次数把零钱找齐。

所以过程是：50元->10元->5元->2元