1235. 规划兼职工作

发表于 2026-01-13 分类于力扣阅读次数： Waline：本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

二分
排序
划分DP
状态机DP

思路

一、问题描述与抽象

给定 \(n\) 份工作，第 \(i\) 份工作由三元组表示： \[ (s_i, e_i, p_i) \] 其中：

\(s_i\)：工作开始时间
\(e_i\)：工作结束时间
\(p_i\)：完成该工作的收益

要求从中选出若干份互不重叠的工作，使得总收益最大。

不重叠的判定规则

两份工作 \(i, j\) 不冲突 当且仅当： \[ e_i \le s_j \quad \text{或} \quad e_j \le s_i \]

二、问题建模

该问题是经典的 加权区间调度（Weighted Interval Scheduling），本质是：

在一组区间中选择一个不相交子集，使得权值和最大。

这是一个典型的 区间 DP + 二分优化 问题。

三、预处理：排序与索引结构

1. 按结束时间排序

将所有工作按结束时间 \(e\) 升序排序；若结束时间相同，则按开始时间 \(s\) 升序。

排序后的工作记为： \[ 1, 2, \dots, n \] 排序的目的在于：

任何以第 \(i\) 个工作为结尾的最优解，只可能来自前 \(i-1\) 个工作。

2. 构造辅助数组 `ends`

定义数组： \[ \text{ends}[i] = \text{第 } i \text{ 个工作（排序后）的结束时间} \] 该数组是一个单调不减序列，后续用于二分查找。

四、状态定义

定义动态规划状态： \[ f[i] = \text{在前 } i \text{ 个工作中，所能获得的最大收益} \] 其中：

工作编号均指 排序后 的顺序
\(f[0] = 0\)，表示不选任何工作时的收益

五、关键子问题：寻找可衔接的前驱工作

对于第 \(i\) 个工作（排序后），其开始时间为 \(s_i\)。

需要找到最大的下标 \(j\)，满足： \[ \text{ends}[j] \le s_i \] 即：

在第 \(i\) 个工作开始之前，最后一个不冲突的工作。

由于 ends 单调递增，可以使用二分查找： \[ j = \max \{ k \mid 1 \le k < i,\ \text{ends}[k] \le s_i \} \] 在代码中，该操作可用：

1	upper_bound(ends, ends + (i - 1), s_i) - ends

其返回值正好是满足条件的工作数量，也即 \(j\)。

六、状态转移方程

对于第 \(i\) 个工作，有两种选择：

不选第 \(i\) 个工作

\[ f[i] = f[i-1] \]

选第 \(i\) 个工作

\[ f[i] = f[j] + p_i \]

其中 \(j\) 为第 \(i\) 个工作的最近不冲突前驱。

最终状态转移：

\[ \boxed{ f[i] = \max\left( f[i-1],\ f[j] + p_i \right) } \]

七、初始化与答案

初始条件： \[ f[0] = 0 \]
最终答案： \[ f[n] \]

八、时间与空间复杂度分析

排序：\(O(n \log n)\)
每个状态一次二分：\(O(\log n)\)
DP 总复杂度： \[ O(n \log n) \]
空间复杂度： \[ O(n) \]

九、AC代码

class Solution {
public:
    static const int maxn = 5e4 + 5;

    // 每个工作：开始时间 s，结束时间 e，收益 p
    struct node {
        int s, e, p;
    };

    // 按结束时间升序排序；若相同，按开始时间升序
    struct cmp {
        bool operator()(const node& a, const node& b) {
            if (a.e != b.e)
                return a.e < b.e;
            return a.s < b.s;
        }
    };

    int jobScheduling(vector<int>& startTime,
                      vector<int>& endTime,
                      vector<int>& profit) {
        int n = startTime.size();

        // 工作数组
        node a[maxn];

        // ends[i]：第 i 个（排序后）工作的结束时间
        int ends[maxn];

        // f[i]：前 i 个工作能获得的最大收益
        int f[maxn];

        // 构造工作数组
        for (int i = 0; i < n; ++i)
            a[i] = {startTime[i], endTime[i], profit[i]};

        // 按结束时间排序
        sort(a, a + n, cmp());

        // 构造 ends 数组（单调不减）
        for (int i = 0; i < n; ++i)
            ends[i] = a[i].e;

        // DP 初始化
        f[0] = 0;

        // 状态转移
        for (int i = 1; i <= n; ++i) {
            int s = a[i - 1].s;  // 当前工作开始时间
            int p = a[i - 1].p;  // 当前工作收益

            // 在 ends[0..i-2] 中找最后一个 <= s 的位置
            // j 表示可选的前驱工作数量
            int j = upper_bound(ends, ends + (i - 1), s) - ends;

            // 不选 or 选 当前工作
            f[i] = max(f[i - 1], f[j] + p);
        }

        return f[n];
    }
};

十、小结

本题的核心在于 排序后的一维 DP 建模
关键难点是： 如何高效找到“最近的不冲突前驱”
利用结束时间的单调性，引入二分查找，使问题从 \(O(n^2)\) 优化至 \(O(n \log n)\)

该模型在区间调度、会议安排、项目选择等问题中具有高度通用性。

考点

思路