LeetCode 1235. 规划兼职工作

约 5 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 5-10 字节 阿里 华为
标签
数组 动态规划 排序 二分查找

题目描述

✅ 1235. 规划兼职工作

image-20260929000800736

image-20260929000800737

题意分析

每份工作由开始时间、结束时间和收益组成，选择若干时间互不重叠的工作，使总收益最大。上一份工作结束的时刻可以直接开始下一份，因此两份工作能衔接的条件是前者结束时间不大于后者开始时间。

解法：按结束时间排序 + 动态规划 + 二分

核心思路

[!blue]

工作收益不同，尽早结束只能为后续留下更多时间，不能保证总收益最大。需要比较“选择当前工作”和“保留之前方案”两种情况。

先将每份工作的三个属性绑定，按结束时间排序。定义 dp[i] 为只考虑排序后前 i 份工作时的最大收益，dp[0] = 0 表示没有工作可选。当前工作是 jobs[i - 1]，如果不选它，答案就是 dp[i - 1]。

如果选择当前工作，它一定是所选方案中最后结束的工作。其他工作都必须在它开始前结束；这些候选按结束时间排序后恰好构成一个前缀。设前缀有 pre 份工作，最优收益就是 dp[pre] + 当前收益。这里使用前缀的最优安排，而不是把前缀中的所有收益直接相加，因为候选之间仍可能重叠。

所有方案都属于选或不选当前工作这两类，因此 dp[i] = max(dp[i - 1], dp[pre] + 当前收益)。选择当前工作后，若此前安排不是该前缀的最优方案，就能替换成 dp[pre] 而不影响衔接，所以这个转移不会遗漏最优解。

在当前工作之前的下标范围 [0, i - 1) 内，二分第一个结束时间严格大于当前开始时间的位置。它前面的工作都可以衔接，所以返回的位置恰好等于数量 pre，可直接用作 DP 下标。没有可衔接工作时 pre = 0，也能通过 dp[0] 自然处理。

解题步骤

  1. 将开始时间、结束时间和收益组成工作记录，按结束时间排序，并提取有序的 ends。
  2. 创建长度为 n + 1 的 dp，初始 dp[0] = 0。
  3. 依次处理前 i 份工作，在此前的 i - 1 份中二分得到可衔接前缀长度 pre。
  4. 比较 dp[i - 1] 和 dp[pre] + 当前工作收益，保存较大值。
  5. 返回 dp[n]。

代码实现

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];

        for (int i = 0; i < n; i++) {
            jobs[i][0] = startTime[i];
            jobs[i][1] = endTime[i];
            jobs[i][2] = profit[i];
        }

        Arrays.sort(jobs, (a, b) -> Integer.compare(a[1], b[1]));

        int[] ends = new int[n];

        for (int i = 0; i < n; i++) {
            ends[i] = jobs[i][1];
        }

        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int[] job = jobs[i - 1];
            // 查第一个结束晚于开始的位置，得到可衔接前缀数量
            int pre = upperBound(ends, i - 1, job[0]);

            // 比较不选与选择当前工作，不能强制覆盖历史最优
            dp[i] = Math.max(dp[i - 1], dp[pre] + job[2]);
        }

        return dp[n];
    }

    private int upperBound(int[] ends, int right, int target) {
        int left = 0;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (ends[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

import "sort"

type Job struct {
    start  int
    end    int
    profit int
}

func jobScheduling(startTime []int, endTime []int, profit []int) int {
    n := len(startTime)
    jobs := make([]Job, n)
    for i := 0; i < n; i++ {
        jobs[i] = Job{start: startTime[i], end: endTime[i], profit: profit[i]}
    }
    sort.Slice(jobs, func(i, j int) bool {
        return jobs[i].end < jobs[j].end
    })

    ends := make([]int, n)
    for i := 0; i < n; i++ {
        ends[i] = jobs[i].end
    }

    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        job := jobs[i-1]
        // 查第一个结束晚于开始的位置，得到可衔接前缀数量
        pre := sort.Search(i-1, func(idx int) bool {
            return ends[idx] > job.start
        })
        // 比较不选与选择当前工作，不能强制覆盖历史最优
        take := dp[pre] + job.profit
        if take > dp[i-1] {
            dp[i] = take
        } else {
            dp[i] = dp[i-1]
        }
    }
    return dp[n]
}

复杂度分析

  • 时间复杂度：$O(n\log n)$，n 为工作数量，排序及每份工作的一次二分占主导。
  • 空间复杂度：$O(n)$，工作、结束时间和 DP 数组。

关键点总结

[!green]

  • 按结束时间排序，是为了让所有可衔接的前置工作形成连续前缀。
  • 等于开始时间的结束值允许衔接，所以查找第一个严格更大的结束时间。
  • dp[i] 是前 i 份工作的最优收益，不要求选中第 i 份工作。

易错点总结

[!yellow]

  • 分开排序三个数组会拆散工作数据。
  • 只算选择当前，可能覆盖更优历史结果。
  • 把二分返回数量再减一，错用了前缀 DP 索引。

相似题目

题目 难度 关联与区别
435. 无重叠区间 中等 原题所有区间收益相同可按结束时间贪心，本题收益不同，需比较选与不选的加权DP。
1031. 两个无重叠子数组的最大和 中等 原题只选两个固定长度窗口，本题任务区间与收益一般化，需要二分前一个不冲突任务。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/79286271
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！