LeetCode 1235. 规划兼职工作

Categories:

题目描述
思路分析
1. 解法一：按结束时间排序 + 动态规划（推荐）
相似题目

题目描述

✅ 1235. 规划兼职工作

思路分析

解法一：按结束时间排序 + 动态规划（推荐）

核心思路：

将每份工作视为区间 [start, end)，按结束时间升序排序。

设 dp[i] 表示前 i 份工作（按结束时间排序后）可获得的最大收益。

对第 i 份工作，用二分查找找到最后一个结束时间不超过其开始时间的工作位置 j，转移为 dp[i] = max(dp[i-1], dp[j] + profit[i])。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示工作数量。

空间复杂度：O(n)，用于保存 DP 与结束时间数组。

import java.util.Arrays;

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) -> a[1] - b[1]);

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

        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int s = jobs[i - 1][0];
            int p = jobs[i - 1][2];

            // 二分查找最后一个结束时间 <= s 的位置
            int l = 0, r = i - 1;
            while (l < r) {
                int mid = (l + r + 1) >>> 1;
                if (ends[mid] <= s) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }

            dp[i] = Math.max(dp[i - 1], dp[l] + p);
        }

        return dp[n];
    }
}

import "sort"

func jobScheduling(startTime []int, endTime []int, profit []int) int {
	n := len(startTime)
	jobs := make([][3]int, n)
	for i := 0; i < n; i++ {
		jobs[i] = [3]int{startTime[i], endTime[i], profit[i]}
	}

	sort.Slice(jobs, func(i, j int) bool {
		return jobs[i][1] < jobs[j][1]
	})

	ends := make([]int, n+1)
	for i := 1; i <= n; i++ {
		ends[i] = jobs[i-1][1]
	}

	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		s := jobs[i-1][0]
		p := jobs[i-1][2]

		// 二分查找最后一个结束时间 <= s 的位置
		l, r := 0, i-1
		for l < r {
			mid := (l + r + 1) >> 1
			if ends[mid] <= s {
				l = mid
			} else {
				r = mid - 1
			}
		}

		if dp[l]+p > dp[i-1] {
			dp[i] = dp[l] + p
		} else {
			dp[i] = dp[i-1]
		}
	}

	return dp[n]
}

相似题目

题目	难度	考察点
1751. 最多可以参加的会议数目 II	困难	区间 DP
2008. 出租车的最大盈利	中等	区间 DP
435. 无重叠区间	中等	区间贪心
452. 用最少数量的箭引爆气球	中等	区间贪心
1326. 灌溉花园的最少水龙头数	困难	区间贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/79286271