Skip to content

Non-overlapping Intervals⚓︎

Link

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.

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 <= 10^5
  • intervals[i].length == 2
  • -5 * 10^4 <= start_i < end_i <= 5 * 10^4

Solution⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int>& lhs, vector<int>& rhs) {
            return lhs[1] < rhs[1];
        });

        int res = 1, end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= end) {
                res++;
                end = intervals[i][1];
            }
        }

        return intervals.size() - res;
    }
};
  • Time complexity: \(O(n\log n)\);
  • Space complexity: \(O(\log n)\) for sort.