区间调度问题[编辑 | 编辑源代码]

区间调度问题（Interval Scheduling Problem）是贪心算法（Greedy Algorithm）中的经典问题之一，广泛应用于任务调度、资源分配等场景。该问题的目标是：在给定的若干区间（如时间区间）中，选择尽可能多的互不重叠的区间。

问题定义[编辑 | 编辑源代码]

给定一组区间 $S = {[s_{1}, f_{1}), [s_{2}, f_{2}), \dots, [s_{n}, f_{n})}$ ，其中 $s_{i}$ 表示区间的起始点， $f_{i}$ 表示区间的结束点。目标是选择一个子集 $S^{'} \subseteq S$ ，使得 $S^{'}$ 中的区间互不重叠，且 $| S^{'} |$ （即子集的大小）最大化。

示例[编辑 | 编辑源代码]

假设有以下区间：

$[1, 3)$
$[2, 4)$
$[3, 5)$
$[4, 6)$

最优解是选择 $[1, 3)$ 和 $[3, 5)$ 或 $[2, 4)$ 和 $[4, 6)$ ，因为这两组区间互不重叠且数量最多。

贪心算法解法[编辑 | 编辑源代码]

贪心算法通过局部最优选择逐步构造全局最优解。对于区间调度问题，通常有以下几种贪心策略： 1. 最早开始时间优先（Earliest Start Time First） 2. 最短区间优先（Shortest Interval First） 3. 最少冲突优先（Fewest Conflicts First） 4. 最早结束时间优先（Earliest Finish Time First）

其中，最早结束时间优先策略被证明能获得最优解。

算法步骤[编辑 | 编辑源代码]

1. 将所有区间按结束时间 $f_{i}$ 升序排序。 2. 初始化一个空集合 $S^{'}$ ，并选择第一个区间加入 $S^{'}$ 。 3. 遍历剩余的区间，每次选择一个与 $S^{'}$ 中最后一个区间不重叠的区间（即其开始时间 $s_{i} \geq f_{last}$ ），并将其加入 $S^{'}$ 。 4. 返回 $S^{'}$ 。

代码实现[编辑 | 编辑源代码]

以下是使用 Python 实现的贪心算法：

def interval_scheduling(intervals):
    # 按结束时间升序排序
    intervals.sort(key=lambda x: x[1])
    selected = []
    last_finish = -float('inf')
    
    for start, finish in intervals:
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish
    
    return selected

# 示例输入
intervals = [(1, 3), (2, 4), (3, 5), (4, 6)]
result = interval_scheduling(intervals)
print("选中的区间：", result)

输出：

选中的区间： [(1, 3), (3, 5)]

算法分析[编辑 | 编辑源代码]

时间复杂度：排序步骤为 $O (n \log n)$ ，遍历区间为 $O (n)$ ，因此总时间复杂度为 $O (n \log n)$ 。
空间复杂度： $O (1)$ （如果不考虑存储结果的空间）。

实际应用案例[编辑 | 编辑源代码]

区间调度问题的应用场景广泛，例如： 1. 会议室预订：选择最多不冲突的会议安排。 2. 课程表安排：避免课程时间冲突。 3. 任务调度：在有限资源下执行最多的任务。

示例：会议室预订[编辑 | 编辑源代码]

假设某公司有多个会议请求，每个会议有开始和结束时间。目标是安排最多的会议，且会议室同一时间只能用于一个会议。

给定会议时间：

会议 A: [9:00, 10:00)
会议 B: [9:30, 10:30)
会议 C: [10:00, 11:00)
会议 D: [11:00, 12:00)

最优解是选择会议 A 和会议 C 或会议 A 和会议 D。

可视化示例[编辑 | 编辑源代码]

以下是一个区间调度的 Mermaid 图示：

变种问题[编辑 | 编辑源代码]

区间调度问题有多种变体，例如： 1. 加权区间调度：每个区间有权重，目标是最大化总权重。 2. 多资源调度：有多个资源（如多个会议室），如何安排最多的区间。 3. 区间着色：用最少的颜色给区间着色，使得重叠区间颜色不同。

总结[编辑 | 编辑源代码]

区间调度问题是贪心算法的典型应用，通过选择最早结束的区间可以高效地找到最优解。该问题在任务调度、资源分配等领域有重要应用。初学者可以通过代码实现和示例加深理解，而高级用户可以进一步探索其变种问题。