Job Sequencing Problem

Q: 作业排序问题的时间复杂度是多少？

使用不相交集合时，时间复杂度为 O(n log n) ，主要由排序决定，空间复杂度为 O(n) 。从每个截止时间开始向前扫描，寻找空闲时段，在大多数截止时间都较大时，耗时为 O(n²) 。

中等贪心排序

+10

你会得到 n 个任务，它们由两个数组表示：如果任务 i 在时间 deadline[i] 前完成，就能获得 profit[i] 的收益。每个任务需要 1 个时间单位，你从时间 0 开始，每次运行一个任务，也可以跳过任意任务。截止时间为 2 的任务可以在 0 到 1 或 1 到 2 之间运行。

返回你能获得的最大总收益。

函数

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: 每项任务必须完成的时间，从 1 到 n
profitinteger-array: 每项工作获得的收益；profit[i] 对应 deadline[i]
返回值integer: 所有工作都能在各自截止日期前完成时的最大总利润

约束条件

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n，其中 n 是作业数量
1 ≤ profit[i] ≤ 10⁵
这些数组未排序。多个工作可能具有相同的截止日期或利润。

示例

输入: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
输出: 120
解释: 两个截止时间为 1 的任务中只能安排一个，所以运行价值为 50 的任务。价值为 30 的任务随后在截止时间 2 完成，价值为 40 的任务则在截止时间 3 完成：50 + 30 + 40 = 120。

输入: deadline = [1, 1, 1]profit = [5, 9, 7]
输出: 9
解释: 这 3 项工作都必须在时间 1 前完成，而在此之前只能安排 1 项工作。它们中收益最高的是 9。

进阶

如果工作 i 需要 duration[i] 个时间单位，而不是 1 个时间单位呢？优先选择利润最高的工作，仍然能获得最高总利润吗？

题解

你可以选择保留哪些工作，以及何时运行它们。一个贪心规则就能同时解决这两个问题：按利润从高到低选择工作，并将每项工作安排在截止时间当天或之前最晚的空闲时段；如果没有空闲时段，就跳过这项工作。并查集可以找到这个时段，而无需逐个检查已经占用的时段。

按利润进行贪心选择，查找空闲时段

思路

把时间划分为多个时隙：时隙 t 的范围是从 t-1 到 t，截止时间为 d 的任务可以使用时隙 1 到 d，并且截止时间都不超过 n。先安排利润最高的任务是安全的：如果它能使用的所有时隙都已被占用，那么用它替换其中一个时隙里的任务，获得的利润至少一样多。安排在最晚的时隙也是安全的，因为截止时间较早的任务只能使用较早的时隙。

开销来自扫描。当每个截止时间都是 n 时，第 k 个任务会越过 k-1 个已占用的时隙：大约需要 n²/2 步；当 n = 5000 时，需要 12.5 million 步。

算法

按利润从大到小对工作排序，并保留每个工作的截止时间和利润。
创建一个包含 n + 1 个标记的数组 taken，并将它们全部设为 false。
对于每个工作，让 t 从其截止时间开始递减到 1，并在找到第一个未被占用的时间槽时停止。
如果找到了这样的时间槽，就将其标记为已占用，并把该工作的利润加到 total 中。
返回 total。

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

使用并查集管理空闲时段，按利润进行贪心选择

思路

扫描会反复遍历相同的已占用时段。对时段 0 到 n 使用并查集可以跳过这些时段：当时段 t 空闲时，设置 parent[t] = t；预订该时段后，设置 parent[t] = t-1，这样从截止时间开始沿指针查找，就能找到最近的空闲时段。到达时段 0 表示没有剩余时段。路径减半会让经过的每个时段指向前方两步的位置，因此后续查找会更短。

在第三个示例中，价值为 60 和 50 的任务分别预订时段 2 和 1。价值为 20、截止时间为 2 的任务沿着 2 到 1，再到 0，因此会被跳过。

排序的时间复杂度为 O(n log n)，使用路径减半后，每次查找的摊还时间复杂度为 O(log n)，因此总时间复杂度仍为 O(n log n)。

算法

按利润从高到低对工作进行排序，并保留每项工作的截止时间和利润。
将从 0 到 n 的每个时段 t 的 parent[t] = t。
对于每项工作，从 slot = deadline 开始，沿着 parent 查找，直到 parent[slot] == slot，并在查找过程中折半路径。
如果 slot > 0，就累加这项工作的利润，并设置 parent[slot] = slot-1；否则跳过这项工作。
返回总计。

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

易错点和边界情况

把任务放进最早的空闲时隙。第三个示例中，价值为 60 的任务会占用时隙 1，价值为 50 的任务则会被舍弃：收益是 80，而不是 110。
按截止时间顺序处理任务。截止时间为 [1, 1]、利润为 [1, 100] 时，利润较低的任务会占用唯一的时隙，你只能获得 1，而不是 100。
将时隙数组的大小设为 n，而不是 n + 1。这样，截止时间等于 n 时，就会越界读取。
单独对利润排序。每个截止时间都必须和对应的利润一起移动。
用递归编写查找步骤。经过数千个已占用时隙的链可能导致栈溢出；请使用循环。

常见问题3

作业排序问题的时间复杂度是多少？

使用不相交集合时，时间复杂度为 O(n log n)，主要由排序决定，空间复杂度为 O(n)。从每个截止时间开始向前扫描，寻找空闲时段，在大多数截止时间都较大时，耗时为 O(n²)。

为什么贪心策略适用于作业排序？

某个最优日程包含利润最高的工作。如果它被排除在外，且截止时间之前有空闲时段，加入它就能获得更多利润；如果这些时段都已安排工作，将它换进去也至少能获得同样多的利润。对剩下的工作重复这个论证即可。

能否改用堆来解决作业排序问题？

是的。按截止时间对工作进行排序，并将每项工作的利润放入最小堆中。每当堆中的工作数量超过当前截止时间允许的数量时，就弹出最小的利润。最后，堆中保留的就是最佳工作集合，其利润总和就是答案，时间复杂度为 O(n log n)。

def jobSequencing(deadline, profit):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

预期输出