435. Non-overlapping Intervals

1. Description

Given an array of intervals intervals where intervals[i] = [$start_i$, $end_i$], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

2. Example

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.

3. Constraints

• 1 <= intervals.length <= 10$^{5}$
• intervals[i].length == 2
• -5 * 10$^{4}$ <= start$_i$ < end$_i$ <= 5 * 10$^{4}$

4. Solutions

Sort && Greedy

n = intervals.size()
Time complexity: O(nlogn)
Space complexity: O(logn)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>> intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[0] < b[0] || a[0] == b[0] && a[1] < b[1];
        });

        const int n = intervals.size();
        int count = 0;
        for (int i = 1, span = intervals[0][1]; i < n; ++i) {
            if (span > intervals[i][0]) {
                ++count;

                span = min(span, intervals[i][1]);
            } else {
                span = intervals[i][1];
            }
        }

        return count;
    }
};