題目

#

leetcode 435 - Non-overlapping Intervals (題目說明請點連結)

題目簡述

#

給一個區間陣列 intervals，其中 intervals[i] = [starti, endi]，請找出需要移除的最少區間數量，使得剩餘的區間沒有重疊。
注意：區間的重疊是指兩個區間有共同的點，例如 [1,2] 和 [2,3] 在點 2 處重疊。

範例

#

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: 移除 [1,3] 後，剩餘的區間 [1,2],[2,3],[3,4] 沒有重疊。

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: 需要移除兩個區間，只保留一個區間。

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: 這些區間沒有重疊，不需要移除任何區間。

解題思路

#

這題要求我們找出需要移除的最少區間數量，使得剩餘的區間沒有重疊。我們可以使用貪心來解決這個問題，具體方法是按照區間的結束時間排序，然後選擇不重疊的區間。

解法

#

貪心

1. 按照區間的結束時間對陣列進行排序
2. 維護一個變數 end 記錄當前選中區間的結束時間
3. 遍歷排序後的區間，選擇不重疊的區間
4. 計算需要移除的區間數量

步驟

#

• 排序：
  • 按照區間的結束時間 end 對陣列進行升序排序
• 初始化：
  • 設定計數器 count = 0 記錄選中的區間數量
  • 設定 end = Integer.MIN_VALUE 記錄當前選中區間的結束時間
• 遍歷區間：
  • 對於每個區間，檢查其開始時間是否大於等於 end
  • 如果不重疊，則選中該區間，更新 end 和 count
• 返回結果：
  • 返回 intervals.length - count，即需要移除的區間數量

例子說明

#

intervals = [[1,2],[2,3],[3,4],[1,3]]

最終結果： 需要移除 1 個區間

貪心選擇過程說明：

• 選中 [1,2]：結束時間為 2，作為第一個不重疊區間
• 選中 [2,3]：開始時間 2 ≥ 結束時間 2，不重疊，選中
• 跳過 [1,3]：開始時間 1 < 結束時間 3，重疊，跳過
• 選中 [3,4]：開始時間 3 ≥ 結束時間 3，不重疊，選中

最終選中的區間： [1,2], [2,3], [3,4] 需要移除的區間： [1,3]

完整程式碼

#

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 按照區間的結束時間進行升序排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        
        // 計數器：記錄選中的不重疊區間數量
        int count = 0;
        // 記錄當前選中區間的結束時間
        int end = Integer.MIN_VALUE;

        // 遍歷排序後的區間
        for(int[] interval : intervals){
            // 檢查當前區間是否與已選中的區間重疊
            if(interval[0] >= end){
                // 如果不重疊，選中該區間
                end = interval[1];
                count++;
            }
            // 如果重疊，跳過該區間
        }

        // 返回需要移除的區間數量
        return intervals.length - count;
    }
}

時間複雜度

#

• 時間複雜度：O(n log n)，其中 n 是區間的數量
  • 排序區間：O(n log n)
  • 遍歷區間：O(n)
  • 總時間複雜度為 O(n log n)
• 空間複雜度：O(1)
  • 只使用了常數個變數來儲存中間結果
  • 排序可能使用額外空間，但題目允許修改原陣列
  • 總空間複雜度為 O(1)