Non-overlapping Intervals

題目描述

給定區間陣列 intervals，回傳需要移除的最少區間數量，使剩餘區間互不重疊。邊界相觸（如 [1,2] 和 [2,3]）不算重疊。

輸入：intervals = [[1,2],[2,3],[3,4],[1,3]]
輸出：1
解釋：移除 [1,3] 後，剩餘的 [1,2],[2,3],[3,4] 不重疊

輸入：intervals = [[1,2],[1,2],[1,2]]
輸出：2

解題思路

按結束時間排序

結束越早的區間排在前面，例如 [[1,3],[1,2],[2,3],[3,4]] 排完後為 [[1,2],[1,3],[2,3],[3,4]]

貪心選擇

選第一個區間 [1,2]，記錄 prevEnd = 2

遍歷判斷

下一個區間的 start ≥ prevEnd → 不重疊，保留它並更新 prevEnd 為它的 end

重疊則移除

start < prevEnd → 重疊，removed++ 但不更新 prevEnd（保留結束較早的那個）

統計移除數

遍歷結束後 removed 就是答案，本例移除 [1,3] 一個區間

程式碼

C#

csharp

public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        // 按結束時間排序
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        
        int removed = 0;
        int prevEnd = intervals[0][1];
        
        for (int i = 1; i < intervals.Length; i++) {
            if (intervals[i][0] < prevEnd) {
                removed++; // 重疊，移除當前區間
            } else {
                prevEnd = intervals[i][1]; // 不重疊，更新結束時間
            }
        }
        return removed;
    }
}

TypeScript

typescript

function eraseOverlapIntervals(intervals: number[][]): number {
    intervals.sort((a, b) => a[1] - b[1]); // 按結束時間排序
    
    let removed = 0;
    let prevEnd = intervals[0][1];
    
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < prevEnd) {
            removed++; // 重疊
        } else {
            prevEnd = intervals[i][1]; // 保留
        }
    }
    return removed;
}

Python

python

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])  # 按結束時間排序
    
    removed = 0
    prev_end = intervals[0][1]
    
    for start, end in intervals[1:]:
        if start < prev_end:
            removed += 1  # 重疊，移除
        else:
            prev_end = end  # 不重疊，保留
    
    return removed

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n log n) | O(1) |

Time：排序 O(n log n) + 一次線性掃描 O(n) = O(n log n)，排序是瓶頸
Space：排序可原地完成，只用了 removed 和 prevEnd 兩個額外變數

邊界情況

只有一個區間：不需要移除任何東西，答案為 0
所有區間完全相同（如 [[1,2],[1,2],[1,2]]）：保留 1 個，移除 n-1 個
所有區間不重疊：不需要移除，答案為 0
區間巢狀（如 [[1,10],[2,3],[4,5]]）：按結束時間排序後 [2,3],[4,5] 排在前面，[1,10] 會被判定為重疊而移除，只移除 1 個

圖解

按結束時間排序

第一個→

保留最早結束的

檢查下一個→

下一個開始 < 前一個結束？

是→

重疊 → 移除

→

不重疊 → 保留

圖表展示了貪心決策流程：排序後保留第一個區間，接著逐一檢查後續區間是否與前一個保留的區間重疊。重疊就計入移除數（removed++），不重疊就保留並更新 prevEnd。

進階觀點

💡面試追問

Q: 為什麼按結束時間排序而不是開始時間？ A: 按結束時間排序是 Activity Selection Problem 的經典貪心解法。結束越早的區間佔用越少的時間軸空間，為後面留出最多餘地。按開始時間排序也能解，但遇到重疊時要額外判斷「保留哪個」（保留結束時間較早的，即 prevEnd = min(prevEnd, end)），邏輯更繁瑣。

Q: 等價問題——最多能保留幾個不重疊區間？ A: 答案 = n - 移除數。這就是 Activity Selection Problem 的標準問法，兩題互為正反面。

Q: 和 452. Minimum Number of Arrows 的差異？ A: 本題邊界相觸不算重疊（[1,2] 和 [2,3] 可以共存），452 題邊界相觸算重疊（一支箭在 x=2 可以同時射穿兩者）。程式碼差異在於判斷條件：本題用 <，452 用 >。

Q: 能否用 DP 解？ A: 可以，但效率低。用 LIS 思路（Longest Increasing Subsequence based on end time）可以做到 O(n log n)，但實作遠比貪心複雜且常數更大。面試中貪心是首選。

理解測驗

🤔 為什麼貪心策略是按結束時間排序，而不是按區間長度排序？

🤔 如果兩個區間是 [1,3] 和 [3,5]，它們算重疊嗎？