LeetCode 解題筆記：1288. Remove Covered Intervals

作者：王一哲
日期：2026年7月6日


LeetCode 題目連結：1288. Remove Covered Intervals

解題想法

中等難度題。題目給定數個區間 $intervals$，其中某些區間可以被其它區間覆蓋，假設移除掉被覆蓋的區間，回傳剩下的區間數量。題目給的提示是時間複雜度為 $O(n^2)$ 的寫法，用兩層 for 迴圈，逐一檢查某個區間是否可以被其它區間覆蓋，由於一個區間可能會被多個區間複蓋，還要用另一個陣列記錄被覆蓋的狀態，或是用一個集合記錄被覆蓋的區間。
這一題比較快的寫法是利用排序，將區間先依照起點由小到大排序，如果起點相同，再依照終點由大到小排序，這個步驟的時間複雜度為 $O(n \log n)$。定義目前已經出現的最大終點 max_end = 0，用一個 for 迴圈讀取排序後的區間，如果這個區間的終點 end <= max_end，代表這個區間可以被覆蓋，被覆蓋區間數量 removed 加 1；反之，更新 max_end 為 end；這個步驟的時間複雜度為 $O(n)$。速度會比前一個方法快很多。

Python 程式碼

Runtime: 271 ms, beats 5.08%. Memory: 19.65 MB, beats 47.88%.

class Solution:
    def removeCoveredIntervals(self, intervals) -> int:
        n = len(intervals)
        intervals.sort(key = lambda x : (x[1], -x[0]))
        removed = [False] * n
        for i in range(1, n):
            for j in range(0, i):
                if intervals[j][0] >= intervals[i][0]:
                    removed[j] = True
        return n - sum(removed[i] for i in range(n))

Runtime: 3 ms, beats 77.50%. Memory: 19.64 MB, beats 47.88%.

class Solution:
    def removeCoveredIntervals(self, intervals) -> int:
        n = len(intervals)  # 數量
        # 排序區間，起點遞增、終點遞減
        intervals.sort(key = lambda x : (x[0], -x[1]))
        removed = 0  # 移除的區間數量
        max_end = 0  # 目前已經出現過的最大終點
        for start, end in intervals:  # 各區間的起點、終點
            if max_end >= end:  # 目前的最大終點可以覆蓋這個區間
                removed += 1  # 數量加 1
            else:  # 反之，更新 max_end
                max_end = end
        return n - removed  # 回傳答案

C++ 程式碼

Runtime: 75 ms, beats 6.09%. Memory: 15.26 MB, beats 30.60%.

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = (int)intervals.size();
        vector<bool> removed (n, false);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if (i == j) continue;
                if (intervals[i][0] <= intervals[j][0] && intervals[i][1] >= intervals[j][1]) {
                    removed[j] = true;
                }
            }
        }
        int tot = 0;
        for(int i = 0; i < n; i++) {
            if (removed[i]) tot++;
        }
        return n - tot;
    }
};

Runtime: 0 ms, beats 100.00%. Memory: 15.23 MB, beats 30.60%. 程式碼第 6 行的 lambda function 如果寫成底下這樣速度會很慢。

[](vector<int> a, vector<int> b) {

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = (int)intervals.size();  // 數量
        // 排序區間，起點遞增、終點遞減
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0]) return a[1] > b[1];
            return a[0] < b[0];
        } );
        int removed = 0, max_end = 0;  // 移除的區間數量，目前已經出現過的最大終點
        for(const auto& it : intervals) {  // 各區間的起點、終點
            if (max_end >= it[1]) {  // 目前的最大終點可以覆蓋這個區間
                removed++;  // 數量加 1
            } else {  // 反之，更新 max_end
                max_end = it[1];
            }
        }
        return n - removed;  // 回傳答案
    }
};