小学四年级也能掌握的贪心算法（6、第 6 课：时间管理大师——区间与任务安排）

贪心算法

第 6 课：时间管理大师——区间与任务安排

上一课，我们认识了活动安排大师。

我们学会了一个非常重要的方法：

按照活动的结束时间从小到大排序，每次选择能够接上的活动。

今天，我们继续进入贪心王国！

这一次，我们不再只是安排活动，而是要帮助一位小小魔法师安排一天的学习和冒险任务。

他一天的时间有限，任务有很多，应该怎样安排才能完成更多任务呢？

今天，我们要把上一课的知识迁移到更丰富的场景中。

一、魔法师的一天：时间不够用了！

小明是一位魔法学校的学生。

今天，他有很多事情要做：

• 练习魔法；

• 制作魔法药水；

• 参加飞行训练；

• 整理魔法书；

• 帮助老师打扫教室；

• 参加魔法比赛。

可是，小明只有一天的时间。

每件事情都有自己的开始时间和结束时间，而且一旦开始，就必须连续完成，中途不能暂停。

他的任务安排如下：

任务

开始时间

结束时间

小明遇到了一个问题：

如果任务之间不能重叠，怎样安排才能完成最多的任务？

大家先想一想：

今天，我们就用贪心算法来解决。

二、先认识什么是区间

在算法中，一个任务可以用两个时间表示：

• 开始时间 start

• 结束时间 finish

例如：

任务A：8点开始，10点结束

我们可以把它看成一个时间区间：

像这样，由开始时间和结束时间组成的一段范围，我们称为区间。

生活中有很多区间：

• 上课时间：8:00—9:00；

• 体育训练：9:00—10:00；

• 看书时间：10:00—10:30；

• 电影播放：14:00—16:00。

它们都有开始和结束。

什么叫区间冲突？

假设：

• 任务 A：8—10；

• 任务 B：9—11。

A 还没有结束，B 就开始了。

两个任务的时间重叠，因此不能同时完成。

如果：

• 任务 A：8—10；

• 任务 B：10—12。

那么 A 在 10 点结束，B 正好在 10 点开始。

这两个任务可以连续完成！

这和上一课的活动安排问题完全一样。

三、第一种任务安排：一天最多完成多少件事？

我们先解决一个最简单的问题：

假设每个任务都一样重要，我们只关心完成的任务数量，最多能完成多少件？

这时，上一课的贪心策略就可以直接使用。

第一步：按照结束时间排序

我们把任务按照结束时间从小到大排列。

原来的任务：

任务

开始时间

结束时间

排序以后：

顺序

任务

开始时间

结束时间

第二步：从前往后选择

我们使用上一课的规则：

如果当前任务的开始时间 >= 上一个任务的结束时间
就选择它；
否则跳过。

逐个检查：

任务

时间

判断

结果

最终选择：

这里要特别提醒大家：

任务安排问题和活动安排问题，本质上是同一个问题。

只是故事换了，算法没有变！

四、第二种任务安排：每件任务都有不同的价值

接下来，难度增加了。

老师告诉小明：

“现在不是所有任务都一样重要了，每完成一件任务，都可以获得不同数量的魔法星星！”

任务变成了这样：

任务

开始

结束

奖励

这次的目标改变了：

不是完成最多的任务，而是获得最多的魔法星星！

我们还能直接使用刚才的贪心策略吗？

1. 如果仍然按照结束时间排序

我们刚才选出了：

B、C、E、F。

获得的奖励是：

10+50+20+60=140 

一共获得 140 颗星星。

2. 如果优先选择奖励最高的任务

G 的奖励最高，有 100 颗星星。

可是 G 的时间是 13—15。

我们可以再选择 B（8—9）和 G（13—15）。

总奖励：

 10+100=110 

比 140 还少。

3. 如果优先选择奖励最高且能够安排的组合

我们还可以选择：

• A：8—10，奖励 30；

• C：9—11，奖励 50；

• F：12—14，奖励 60；

• G：13—15，奖励 100。

但是注意，这些任务之间存在时间冲突，不能全部选择。

例如 C 和 A 冲突，G 和 F 冲突。

我们必须在任务数量、时间冲突和奖励之间进行综合考虑。

重要发现

当目标从“完成最多任务”变成“获得最高奖励”时，原来的贪心规则不一定还能得到最优结果。

我们需要考虑不同任务组合的总奖励。

这里就可以自然引出下一阶段要学习的动态规划。

今天先让同学们认识这个区别。

五、第三种任务安排：任务有截止时间

我们再来看看另一种更有趣的情况。

小明接到了老师的 4 个任务。

每个任务都需要 1 个小时完成，而且每个任务都有一个最后完成时间。

任务

完成需要时间

截止时间

奖励

这里的截止时间表示：

• A 必须在第 1 个小时结束前完成；

• B、C 必须在第 2 个小时结束前完成；

• D 必须在第 3 个小时结束前完成。

我们最多只有 3 个小时。

目标是：

合理安排任务，让获得的奖励尽可能多。

1. 先按照奖励从大到小排序

顺序

任务

截止时间

奖励

这次，我们优先考虑奖励高的任务。

2. 安排任务

我们可以把时间分成 3 个格子：

为什么 B 没有选？

因为 B 的截止时间是第 2 小时结束，前两个小时已经安排了 A 和 C。

而且 A、C、D 的总奖励是：

 50+40+30=120 

如果选择 B 替换 C：

50+20+30=100 

所以不如原来的安排。

这类问题叫作带截止时间的任务调度问题。

对于“每个任务耗时相同、每个任务只能安排一次”的经典版本，可以使用贪心算法：

3. C++ 程序

为了让初学者容易理解，我们先使用一个简单的数组模拟时间格子。

#include <iostream>
#include <algorithm>
using namespace std;

struct Task {
int id; // 任务编号
int deadline; // 截止时间
int value; // 奖励
};

// 按照奖励从大到小排序
bool cmp(Task a, Task b) {
return a.value > b.value;
}

int main() {
int n = 4;

Task a[100] = {
{1, 1, 50},
{2, 2, 20},
{3, 2, 40},
{4, 3, 30}
};

sort(a, a + n, cmp);

// 每个时间格子只能安排一个任务
int used[100] = {0};

int ans = 0;

for (int i = 0; i < n; i++) {
// 从截止时间向前找空闲位置
for (int j = a[i].deadline; j >= 1; j–) {
if (used[j] == 0) {
used[j] = a[i].id;
ans += a[i].value;
break;
}
}
}

cout << "总奖励：" << ans << endl;

cout << "任务安排：";
for (int i = 1; i <= 3; i++) {
if (used[i] != 0) {
cout << used[i] << " ";
}
}

return 0;
}

输出：

总奖励：120
任务安排：1 3 4

4. 这段代码最重要的地方

for (int j = a[i].deadline; j >= 1; j–) {
if (used[j] == 0) {
used[j] = a[i].id;
ans += a[i].value;
break;
}
}

我们来逐句理解：

• j = a[i].deadline：先尝试把任务放在最晚允许的时间。

• j >= 1：如果这个位置已经被占用，就继续向前找。

• used[j] == 0：检查这个时间格子是不是空闲。

• used[j] = a[i].id：把任务放进去。

• ans += a[i].value：把奖励加起来。

• break：任务已经安排成功，不需要继续寻找。

为什么要尽量安排在截止时间之前最靠后的空闲位置？

因为这样可以把前面的时间留给那些截止时间更早的任务。

注意：这个贪心方法有严格的适用条件。 上面的程序假设每个任务都恰好需要 1 个时间单位，且时间从 1 开始。任务耗时不同，就不能直接照搬这个程序。

六、三种任务安排问题对比

今天我们接触了三种不同的问题。

问题

目标

常用算法

这里特别强调：

不是所有带奖励的任务都要用动态规划，也不是所有任务安排都能用贪心。

要先看清楚题目的规则和目标，再决定使用什么算法。

七、课堂练习：小小时间管理师

练习 1：最多完成几个任务？

魔法学校有 5 个任务：

任务

开始时间

结束时间

请回答：

练习 2：任务奖励大比拼

现在有 4 个任务，每个任务都需要 1 小时完成。

任务

截止时间

奖励

请回答：

练习 3：想一想，应该使用什么算法？

请判断：

题目

算法

试着完成练习 3

1、选择最多个互不冲突的活动，排序规则是什么？

A、开始时间从小到大

B、结束时间从小到大

C、奖励从大到小

答案： B

2、单位时间任务调度，如何安排？

A、按奖励排序，放到截止时间前最晚的空位

B、按截止时间排序，依次安排

C、随便安排

答案：A

贪心规律：

3、单位时间任务调度通常使用什么算法？

A、贪心

B、深度优先搜索

C、广度优先搜索

答案：A

八、本课知识总结

今天，我们从活动安排出发，认识了三种任务安排问题。

孩子们需要掌握的重点不是记住所有代码，而是学会先分析题目。

时间安排三步思考法：

第一步：看目标

是想完成最多的任务，还是获得最多的奖励？

第二步：看规则

任务是否允许重叠？每个任务需要多长时间？有没有截止时间？

第三步：选算法

根据目标和规则，判断能不能使用贪心，还是需要动态规划等其他方法。

送给大家一句话：

先看目标，再定规则；

看清条件，选择算法！

下一课：贪心算法第 7 课：魔法工厂的流水线——两台机器怎样配合最快？

怎样安排工件的加工顺序，才能让两台机器尽量少等待，让所有工件尽早加工完成？