区间调度问题

问题概述

给定 n 个任务，每个任务有开始时间 start 和结束时间 end。两个任务不冲突当且仅当后一个任务的开始时间 >= 前一个任务的结束时间（首尾可相接）。

两种常见变体：

最大任务数：每个任务权重相同，求最多能完成多少个任务 → 贪心；
最大利润：每个任务有利润 profit，求最大总利润 → 动态规划 + 二分。

方法一：最大任务数（贪心）

思路及解法

这是经典的活动选择问题。

贪心策略：按结束时间升序排序，依次选择不冲突的任务。

为什么按结束时间排序：

结束得越早，留给后面任务的时间越多；
每次选结束最早且不冲突的任务，能为后续留下最大空间；
这是可以严格证明的贪心最优策略。

流程：

按结束时间升序排序；
维护 last_end 表示上一个被选任务的结束时间，初始为 -inf；
遍历每个任务 (s, e)：
- 若 s >= last_end，说明与已选任务不冲突，选中它，count += 1，last_end = e；
返回 count。

边界说明：

s >= last_end：允许首尾相接（闭区间不重叠）；
若题目要求严格不重叠（首尾不能相等），改成 s > last_end。

代码

def max_tasks(tasks: list[tuple[int, int]]) -> int:
    if not tasks:
        return 0

    # 按结束时间升序排序
    tasks.sort(key=lambda x: x[1])

    count = 0
    last_end = float('-inf')

    for s, e in tasks:
        if s >= last_end:      # 不冲突
            count += 1
            last_end = e

    return count

复杂度分析

时间复杂度：$O(n \log n)$，排序开销。
空间复杂度：$O(1)$ 或 $O(n)$（取决于排序实现）。

示例

tasks = [(1, 3), (2, 5), (4, 7), (6, 9), (8, 10)]
# 排序后：[(1,3), (2,5), (4,7), (6,9), (8,10)]
# 选：(1,3) → (4,7) → (8,10)
# 答案：3

方法二：最大利润（DP + 二分）

思路及解法

每个任务有权重 profit，贪心不再成立，需要用动态规划。

状态定义：dp[i] 表示「前 i 个任务（按结束时间排序后）能获得的最大利润」。

转移方程：

对于第 i 个任务（0-indexed，对应 dp[i+1]）：

不选它：dp[i]；
选它：profit[i] + dp[k]，其中 k 是「最后一个结束时间 <= 当前任务开始时间的任务」的数量。

$dp[i+1] = \max(dp[i],\ dp[k] + profit[i])$

如何快速找 k：

把所有任务的结束时间单独拿出来，因为已按结束时间排序，所以 ends 是升序的；
用 bisect_right(ends, start) 找到第一个 > start 的位置 k，则 ends[0..k-1] 都 <= start，即前 k 个任务都可以作为前驱。

代码

from bisect import bisect_right

def max_profit(jobs: list[tuple[int, int, int]]) -> int:
    """
    jobs: List[(start, end, profit)]
    返回最大利润
    """
    if not jobs:
        return 0

    jobs.sort(key=lambda x: x[1])        # 按结束时间排序
    n = len(jobs)
    ends = [j[1] for j in jobs]          # 结束时间数组（升序）

    dp = [0] * (n + 1)                   # dp[i]：前 i 个任务的最大利润

    for i, (s, e, p) in enumerate(jobs):
        k = bisect_right(ends, s)        # ends[:k] 全部 <= s
        dp[i + 1] = max(dp[i], dp[k] + p)

    return dp[n]

复杂度分析

时间复杂度：$O(n \log n)$，排序 $O(n \log n)$，每次二分 $O(\log n)$，共 $n$ 次。
空间复杂度：$O(n)$，dp 和 ends 数组。

示例

jobs = [
    (1, 3, 50),
    (2, 5, 20),
    (4, 6, 70),
    (6, 7, 60),
    (5, 8, 30),
]
print(max_profit(jobs))  # 180（选 (1,3) + (4,6) + (6,7)）

带路径还原（打印选了哪些任务）

思路及解法

在 DP 的基础上，用 pre[i] 记录 dp[i] 是从哪个状态转移来的：

若 dp[i+1] 来自「不选任务 i」，则 pre[i+1] = i+1（标记为未选）；
若来自「选任务 i」，则 pre[i+1] = k+1（记录前驱状态）。

回溯时从 i = n 开始：

若 pre[i] == i，说明任务 i-1 未被选，i -= 1；
否则任务 i-1 被选，加入结果，i = pre[i] - 1。

代码

from bisect import bisect_right

def max_profit_with_tasks(jobs: list[tuple[int, int, int]]) -> tuple[int, list[tuple[int, int, int]]]:
    if not jobs:
        return 0, []

    jobs.sort(key=lambda x: x[1])
    n = len(jobs)
    ends = [j[1] for j in jobs]

    dp = [0] * (n + 1)
    pre = [0] * (n + 1)

    for i, (s, e, p) in enumerate(jobs):
        k = bisect_right(ends, s)
        if dp[k] + p > dp[i]:
            dp[i + 1] = dp[k] + p
            pre[i + 1] = k + 1          # 选了任务 i，前驱是前 k 个任务
        else:
            dp[i + 1] = dp[i]
            pre[i + 1] = i + 1          # 未选任务 i

    # 回溯
    chosen = []
    i = n
    while i > 0:
        if pre[i] == i:                 # 未选任务 i-1
            i -= 1
        else:
            chosen.append(jobs[i - 1])
            i = pre[i] - 1

    return dp[n], chosen[::-1]

复杂度分析

时间复杂度：$O(n \log n)$。
空间复杂度：$O(n)$，dp、pre、ends 三个数组。

两种问题对比

	最大任务数	最大利润
权重	每个任务权重为 1	每个任务有独立利润
方法	贪心（按结束时间排序）	DP + 二分
时间	$O(n \log n)$	$O(n \log n)$
空间	$O(1)$	$O(n)$
核心	早结束优先	选或不选取最大

关键区别：当所有任务价值相同时，贪心最优；一旦引入不同利润，贪心不再成立，必须用 DP。

边界条件说明

1. 首尾能否相接

代码中统一用 s >= last_end（或 bisect_right），表示首尾可以相接；
若题目要求「严格不重叠」（即前一个任务结束时间必须 < 后一个开始时间），把 >= 改为 >，bisect_right 改为 bisect_left。

2. 利润可能为负

dp[0] = 0 表示「一个任务都不选」，利润为 0；
若某些任务利润为负，DP 会自动选择不选它们，无需特殊处理。

3. 任务允许并行

上述两种方法都假设同一时间只能执行一个任务；
若允许多台机器并行，问题变成「会议室 II」类型，需要求最大重叠数（扫描线 / 最小堆），与本文不同。

总结

最大任务数：贪心，按结束时间排序，依次选不冲突的，$O(n \log n)$；
最大利润：DP + 二分，dp[i+1] = max(dp[i], dp[k] + profit[i])，$O(n \log n)$；
路径还原：用 pre 数组记录转移来源，回溯即可得到选中任务；
边界：首尾是否可相接决定用 >= / >，以及 bisect_right / bisect_left；
通用套路：区间调度 → 按结束时间排序，无权贪心，有权 DP。

区间调度问题

区间调度问题

问题概述

方法一：最大任务数（贪心）

思路及解法

代码

复杂度分析

示例

方法二：最大利润（DP + 二分）

思路及解法

代码

复杂度分析

示例

带路径还原（打印选了哪些任务）

思路及解法

代码

复杂度分析

两种问题对比

边界条件说明

1. 首尾能否相接

2. 利润可能为负

3. 任务允许并行

总结

相关题目