发表于 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 题目链接