Weighted Job Scheduling

Input: Number of Jobs n = 4
Job Details {Start Time, Finish Time, Profit}
Job 1: {1, 2, 50}
Job 2: {3, 5, 20}
Job 3: {6, 19, 100}
Job 4: {2, 100, 200}
Output: The maximum profit is 250.
We can get the maximum profit by scheduling jobs 1 and 4.
Note that there is longer schedules possible Jobs 1, 2 and 3
but the profit with this schedule is 20+50+100 which is less than 250.

YouTube 题解

思路：DP

• 将 job 按 complete time 升序排序
• 状态定义 int[] dpMaxProfit = new int[jobs.length + 1], dp[i] 代表以 jobs[i] 为最后一份 job 所产生的最大收益
• 状态转移方程：dp[i] = max(dp[0 ~ (i-1)]) + jobs[i]
• 初始化: dp[0] = 0
• 循环体：双循环
• 返回值 max(dp[i])

这里的jobs 的profit 是有变化的，如果是单一值，就变成了一个人可以从中做最多多少分工作。Meeting Room 问题就变成，一个人最多可以参加多少会议；一个飞机最多可以飞多少个航班。