題目模型
N 個 TV 節目，每個有開始 `s`、結束 `e`、幸福值 `v`。選擇不重疊節目最大化總幸福值。N≤100000。
解法：排序 + DP + 二分優化
- 按結束時間 `e` 升序排序。
- `dp[i]` = 前 i 個節目 (按結束時間) 的最大幸福值。
`dp[i] = max(dp[i-1], dp[p(i)] + v[i])`
其中 `p(i)` = 最大的 `j < i` 使得 `e[j] <= s[i]` (二分查找)。
- 答案 `dp[N]`。
複雜度
- 排序 O(N log N)，DP O(N log N) (二分)，總 O(N log N)。
參考題解
acmerblog 詳細講解與代碼
