題目網址：https://leetcode.cn/problems/non-overlapping-intervals/

題意：給一區間集合 intervals, 其中 intervals[i] = [start_i, end_i], 返回需要移除的最小區間個數, 使得剩下的區間互不重疊。

Solution：

想法：首先, 先將 intervals 做排序, 然後紀錄前一天的 end, 當有兩天 start 相同時, end 會取較小的那一個, 這樣才能最大化避免重疊

以下圖為例, sorting 後的 intervals = [[1,2], [1,3], [2,3], [3,4], 最一開始 [1,2] 和 [1,3] 我們會選擇捨棄 [1,3], 因為 [1,2] 的 end 較小, 若保留 [1,3] 則會和後面的 [2,3] 重疊

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());

        int res = 0, prevEnd = intervals[0][1];

        for (int i = 1; i < intervals.size(); ++i) {
            // prevEnd > current start, 代表有重疊, 捨棄其中一個, 且 prevEnd 要更新
            if (prevEnd > intervals[i][0]) {
                prevEnd = min(prevEnd, intervals[i][1]);
                ++res;
            } else { // 沒重疊, 則 prevEnd 更新為當前 interval 的 end
                prevEnd = intervals[i][1];
            }
        }

        return res;
    }
};
  • time：$O(n \cdot log(n))$ ➔ sorting
  • space：$O(1)$ ➔ 只需常數空間