1288. Remove Covered Intervals

Medium
Description

給定一組區間 intervals，移除所有被其他區間完全覆蓋的區間。區間 [a,b) 被 [c,d) 覆蓋的條件是 c <= a 且 b <= d。回傳剩餘區間的數量。

Example:

Input: intervals = [[1,4],[3,6],[2,8]] Output: 2 ([1,4] 被 [2,8] 覆蓋，但 [2,8] 不被覆蓋所以實際是 [3,6] 和 [2,8]… 更正：[1,4] 被 [2,8] 覆蓋? 不，1 < 2。讓我重新看：[3,6] 被 [2,8] 覆蓋因為 2<=3 且 6<=8)

Intuition#

核心思路：按起點升序排序（起點相同則按終點降序），然後追蹤目前最大的右端點，若新區間的右端點不超過它就是被覆蓋的。

  • 排序後，起點較小（或相同）的區間排在前面
  • 起點相同時，終點大的排前面——這樣後面的同起點區間一定被覆蓋
  • 遍歷時維護目前最大右端點 maxRight，若當前區間 right <= maxRight 則被覆蓋

Approaches#

⭐1: 排序 + 貪心#

  • 概念: 排序後線性掃描，用 maxRight 追蹤覆蓋範圍
  • 時間複雜度: O(n log n) - 排序主導
  • 空間複雜度: O(log n) - 排序空間
class Solution {
    fun removeCoveredIntervals(intervals: Array<IntArray>): Int {
        // 起點升序，起點相同則終點降序
        intervals.sortWith(compareBy<IntArray> { it[0] }.thenByDescending { it[1] })

        var count = 0
        var maxRight = 0

        for (interval in intervals) {
            if (interval[1] > maxRight) {
                // 不被覆蓋
                count++
                maxRight = interval[1]
            }
            // 否則 interval[1] <= maxRight，被前面的區間覆蓋
        }

        return count
    }
}

2: 暴力兩兩比較#

  • 概念: 對每個區間檢查是否存在另一個區間覆蓋它
  • 時間複雜度: O(n^2) - 兩層迴圈
  • 空間複雜度: O(1)
class Solution {
    fun removeCoveredIntervals(intervals: Array<IntArray>): Int {
        val n = intervals.size
        var removed = 0

        for (i in 0 until n) {
            var covered = false
            for (j in 0 until n) {
                if (i != j &&
                    intervals[j][0] <= intervals[i][0] &&
                    intervals[i][1] <= intervals[j][1]) {
                    covered = true
                    break
                }
            }
            if (covered) removed++
        }

        return n - removed
    }
}

🔑 Takeaways#

  • Pattern: 區間排序 + 貪心掃描——排序策略決定了後續邏輯的簡潔度
  • 關鍵技巧: 起點相同時按終點降序排，保證同起點的大區間在前，後面的小區間自然被覆蓋