Non-overlapping Intervals

Problem

https://leetcode.com/problems/non-overlapping-intervals/

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⁵

• intervals[i].length == 2

• -5 * 10⁴<= start_i< end_i<= 5 * 10⁴

Pattern

Array, Greedy, Intervals, Sorting

Approaches

Greedy

Code

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    """Return the minimum removals to make *intervals* non-overlapping."""
    if not intervals:
        return 0

    intervals.sort()
    result = 0
    prev_end = intervals[0][1]
    for i in range(1, len(intervals)):
        a, b = intervals[i]
        if a < prev_end:
            result += 1
            prev_end = min(prev_end, b)
        else:
            prev_end = b

    return result

Test

>>> from non_overlapping_intervals__greedy import eraseOverlapIntervals
>>> eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]])
1
>>> eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]])
2
>>> eraseOverlapIntervals([[1, 2], [2, 3]])
0

non_overlapping_intervals__greedy.eraseOverlapIntervals(intervals: list[list[int]]) → int

Return the minimum removals to make intervals non-overlapping.