跳到主要内容

区间调度问题

区间调度问题是贪心算法中的经典问题之一。它的核心目标是从一组任务中选择尽可能多的任务，使得这些任务在时间上不重叠。这类问题在实际生活中有广泛的应用，例如会议安排、课程调度等。

问题描述​

假设我们有一组任务，每个任务都有一个开始时间和结束时间。我们的目标是选择尽可能多的任务，使得这些任务在时间上不重叠。换句话说，我们不能同时进行两个任务。

输入​

  • 一组任务，每个任务表示为 [start, end]，其中 start 是任务的开始时间，end 是任务的结束时间。

输出​

  • 一个最大任务集合，这些任务在时间上不重叠。

贪心算法解决思路​

贪心算法的核心思想是每一步都做出局部最优的选择，希望通过这些局部最优的选择最终达到全局最优。对于区间调度问题，我们可以采用以下贪心策略：

  1. 按结束时间排序：将所有任务按照结束时间从早到晚排序。
  2. 选择最早结束的任务：选择第一个任务，并将其加入结果集合。
  3. 排除冲突任务：排除所有与已选任务时间重叠的任务。
  4. 重复步骤2和3：直到所有任务都被处理完毕。

代码示例​

以下是一个使用贪心算法解决区间调度问题的Python代码示例：

python
def interval_scheduling(intervals):
    # 按结束时间排序
    intervals.sort(key=lambda x: x[1])
    
    selected = []
    last_end = -1
    
    for start, end in intervals:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    
    return selected

# 示例输入
intervals = [(1, 3), (2, 5), (3, 6), (5, 7), (6, 8)]
# 调用函数
result = interval_scheduling(intervals)
print("选择的任务区间:", result)

输入和输出​

输入:

python
intervals = [(1, 3), (2, 5), (3, 6), (5, 7), (6, 8)]

输出:

python
选择的任务区间: [(1, 3), (5, 7)]

逐步讲解​

  1. 排序：首先，我们将所有任务按照结束时间从早到晚排序。排序后的任务列表为 [(1, 3), (2, 5), (3, 6), (5, 7), (6, 8)]。

  2. 选择任务：我们从第一个任务 (1, 3) 开始，将其加入结果集合，并记录其结束时间 3。

  3. 排除冲突任务：接下来，我们检查下一个任务 (2, 5)，发现它的开始时间 2 小于 3，因此它与已选任务冲突，跳过。

  4. 继续选择：我们继续检查任务 (3, 6)，发现它的开始时间 3 等于 3，因此它与已选任务冲突，跳过。

  5. 选择下一个任务：我们检查任务 (5, 7)，发现它的开始时间 5 大于 3，因此它与已选任务不冲突，将其加入结果集合，并记录其结束时间 7。

  6. 排除冲突任务：最后，我们检查任务 (6, 8)，发现它的开始时间 6 小于 7，因此它与已选任务冲突，跳过。

  7. 结束：所有任务处理完毕，最终选择的任务为 [(1, 3), (5, 7)]。

实际案例​

会议安排​

假设你是一家公司的会议安排负责人，你需要安排一天中的多个会议。每个会议都有一个开始时间和结束时间。你的目标是安排尽可能多的会议，使得这些会议在时间上不重叠。

课程调度​

在学校中，课程调度也是一个典型的区间调度问题。每个课程都有一个开始时间和结束时间，你需要安排尽可能多的课程，使得这些课程在时间上不重叠。

总结​

区间调度问题是贪心算法中的一个经典问题，通过按结束时间排序并选择最早结束的任务，我们可以有效地解决这个问题。贪心算法的优势在于其简单性和高效性，适用于许多实际场景。

附加资源与练习​

  • 练习1：给定一组任务 [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]，使用贪心算法找出最大不重叠任务集合。
  • 练习2：尝试修改代码，使其能够处理任务权重不同的情况，即选择的任务集合的总权重最大。
提示

贪心算法虽然简单，但并不是所有问题都适用。在使用贪心算法时，务必验证其正确性。