1288. Remove Covered Intervals

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

1288Remove Covered IntervalsIntervalsMediumIntervals

給定一組區間 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

TIP

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

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

Approaches

⭐ 1. Sort + Greedy — O(n log n) / O(log n)

Idea: 排序後線性掃描，用 maxRight 追蹤覆蓋範圍
Time: O(n log n) - 排序主導
Space: 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. Brute Force: Pairwise Compare — O(n^2) / O(1)

Idea: 對每個區間檢查是否存在另一個區間覆蓋它
Time: O(n^2) - 兩層迴圈
Space: 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: 區間排序 + 貪心掃描——排序策略決定了後續邏輯的簡潔度
Key trick: 起點相同時按終點降序排，保證同起點的大區間在前，後面的小區間自然被覆蓋

Intuition

Approaches

🔑 Takeaways

相關題目