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.
思路：DP
- 將 job 按 complete time 升序排序
- 狀態(tài)定義
int[] dpMaxProfit = new int[jobs.length + 1], dp[i] 代表以 jobs[i] 為最后一份 job 所產(chǎn)生的最大收益 - 狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[0 ~ (i-1)]) + jobs[i]
- 初始化: dp[0] = 0
- 循環(huán)體：雙循環(huán)
- 返回值 max(dp[i])
這里的jobs 的profit 是有變化的儒陨，如果是單一值，就變成了一個人可以從中做最多多少分工作嗜愈。Meeting Room 問題就變成琼开，一個人最多可以參加多少會議质涛；一個飛機(jī)最多可以飛多少個航班。
