JZX轻语：简

LeetCode 1235 - 规划兼职工作

发表于2024年05月04日

会议安排题目的带权重版本。在会议安排普通版本的dp解法中，先按结束时间排序，然后令dp[i]为前i个会议中最多能安排的会议数，则有dp[i] = max(dp[i - 1], dp[k] + 1)(即，要么选取第i个会议，要么不选，使用前i - 1个会议的结果)，其中k是指前k个会议的结束时间小于等于第i个会议的开始时间。在带权重的版本中，可以改写成dp[i] = max(dp[i - 1], dp[k] + profit[i])。

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        jobs = sorted(zip(startTime, endTime, profit), key=lambda p: p[1])
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            k = bisect_right(jobs, jobs[i - 1][0], hi=i, key=lambda p: p[1])
            dp[i] = max(dp[i - 1], dp[k] + jobs[i - 1][2])
        return dp[n]

闪念标签：LC

题目链接：https://leetcode.cn/problems/maximum-profit-in-job-scheduling/