MediumRating 1567
435. Non-overlapping Intervals
arraydynamic-programminggreedysorting
解題說明
Non-overlapping Intervals
題目描述：給定一組區間，求需要移除的最少區間數，使剩餘區間互不重疊。
解題思路：貪心：按結束時間排序，盡量保留結束早的區間（為後面的區間留更多空間）。維護上一個保留區間的結束時間 end。對每個區間：若其開始時間 >= end，可以保留，更新 end；否則需要移除（計數加一），保留結束時間較早的那個（即維持較小的 end）。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 排序主導，掃描為 O(n)。
空間複雜度：O(1) — 原地排序，只用常數額外空間。
虛擬碼
1. Sort intervals by end time 2. Set end = -infinity, removals = 0 3. For each interval iv: a. If iv.start >= end: keep it, end = iv.end b. Else: remove it (overlap), removals++ 4. Return removals
其他解法
按開始位置排序：改為按起點排序再用 DP，邏輯更複雜。
二分搜尋 DP O(n log n)：找最後不重疊的區間，用二分而非線性掃描 — 時間複雜度相同但常數不同。
延伸思考
- 若要選最多區間（同時要求不重疊）？
- 若區間有權重，選擇最大權重子集？
- 若區間為開區間 (a, b) 而非閉區間 [a, b]？