Problem

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.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Examples

Example 1:

1
2
3

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:

1
2
3

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:

1
2
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 <= starti < endi <= 5 * 10^4

Solution

Method 1 - Sorting by Start of Interval

We can sort the intervals based on their starting times. Track prevEnd from the previous interval. When comparing two intervals, consider the smaller end value to minimize overlaps with subsequent intervals.

Code

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

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // Sort intervals by their start times
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        int prevEnd = intervals[0][1];
        int count = 0;
        
        for (int i = 1; i < intervals.length; i++) {
            if (prevEnd > intervals[i][0]) {
                count++;
                prevEnd = Math.min(intervals[i][1], prevEnd);
            } else {
                prevEnd = intervals[i][1];
            }
        }
        
        return count;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # Sort intervals by their start times
        intervals.sort(key=lambda x: x[0])
        
        prev_end = intervals[0][1]
        count = 0
        
        for i in range(1, len(intervals)):
            if prev_end > intervals[i][0]:
                count += 1
                prev_end = min(intervals[i][1], prev_end)
            else:
                prev_end = intervals[i][1]
        
        return count

Complexity

  • ⏰ Time complexity: O(n log n) for sorting the intervals.
  • 🧺 Space complexity: - O(1) for space as we use a constant amount of extra space (excluding input).

Method 2 - Sorting by End of Interval

Actually, the problem is similar to classic greedy problem - Interval Scheduling Problem where we are given a collection of intervals, find the maximum number of intervals that are non-overlapping".

Code

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

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        // Sort intervals by their end times
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int end = intervals[0][1];
        int count = 1;

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

        return intervals.length - count;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        # Sort intervals by their end times
        intervals.sort(key=lambda x: x[1])

        end = intervals[0][1]
        count = 1

        for i in range(1, len(intervals)):
            if intervals[i][0] >= end:
                end = intervals[i][1]
                count += 1
        
        return len(intervals) - count

Complexity

  • ⏰ Time complexity: O(n log n) for sorting the intervals.
  • 🧺 Space complexity: O(1) as only a constant amount of extra space is used (excluding input).