435. Non-overlapping Intervals

[fockspaces]

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping. Example 2:

Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping. Example 3:

Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

1 <= intervals.length <= 105 intervals[i].length == 2 -5 104 <= starti < endi <= 5 104

[fockspaces]

這題也是很難想到，先對區間做排序，當遇到重疊，取尾部較前面的 應該算是 greedy 的應用

1. 重疊必取捨 (增加 remove 個數）
2. 取捨策略（取短邊）

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int remove = 0; 
        sort(intervals.begin(), intervals.end());
        vector<int> cur = intervals[0];
        for(int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] >= cur[1]) cur = intervals[i];
            else {
                cur[1] = min(intervals[i][1], cur[1]);
                remove++;
            }
        }
        return remove;
    }
};

[fockspaces]

cur 其實直接以 int 紀錄當前最尾端即可 time : O(NlogN) space：O(1)

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int remove = 0; 
        sort(intervals.begin(), intervals.end());
        int curEnd = intervals[0][1];
        for(int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] >= curEnd) curEnd = intervals[i][1];
            else {
                curEnd = min(intervals[i][1], curEnd);
                remove++;
            }
        }
        return remove;
    }
};

[fockspaces]

We can think it greedy, sorted the list first to get the best arrangment for out strategy.

each time we comes to overlapped, we have to choose either current interval or the newer intervel, our goal is to keep the more intervals as possible. So we'll take the interval whose tail is more front than the other one.

when it's not overlapped, we can simply update the cur_interval into new_interval

we can further simplify this into one variable called cur_tail, since each interval head is strictly increase during iteration.

Time: O(NlogN) for sorting + O(N) for iteration Space: in-place O(1)

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        ans = 0
        cur_end = intervals[0][1]
        for i in range(1, len(intervals)):
            new_interval = intervals[i]
            if cur_end > new_interval[0]:
                ans += 1
                cur_end = min(cur_end, new_interval[1])
            else:
                cur_end = new_interval[1]
        return ans

[MingFaTW]

Time: O(NlogN) + O(N)

Space: O(N)

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        remove = 0
        intervals = sorted(intervals)
        cur_interval = intervals[0]
        for interval in intervals[1:]:
            if self.is_overlapped(cur_interval, interval):
                cur_interval = self.update_interval(cur_interval, interval)
                remove += 1
            else:
                cur_interval = interval
        return remove

    def is_overlapped(self, cur_interval, new_interval):
        return new_interval[0] < cur_interval[1]

    def update_interval(self, cur_interval, new_interval):
        if new_interval[1] < cur_interval[1]:
            return new_interval
        return cur_interval

[MingFaTW]

Time: O(NlogN) + O(N)

Space: O(N)

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        remove = 0
        intervals = sorted(intervals)
        prev_end = intervals[0][-1]
        for start, end in intervals[1:]:
            if self.is_overlapped(prev_end, start):
                prev_end = min(prev_end, end)
                remove += 1
            else:
                prev_end = end

        return remove

    def is_overlapped(self, prev_end, next_start):
        return next_start < prev_end