Non-overlapping Intervals

IntervalsArraysGreedy

25 min

Problem Statement

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

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Initial Intervals:

[1, 2]

[2, 3]

[3, 4]

[1, 3]

Minimum Removals:

Output: 1

Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Solution

This is a classic greedy problem. To minimize removals, we should keep intervals that finish as early as possible. This leaves the maximum amount of room for subsequent intervals.

Algorithm Steps

Sort the intervals based on their end times.
Initialize a counter for removals to 0 and track the end of the last kept interval.
Iterate through the sorted intervals. If the current interval's start is before the end of the last kept interval, it overlaps and must be "removed" (increment counter).
Otherwise, keep the current interval and update the "last end" tracker.

Intervals

[1, 2]

[2, 3]

[3, 4]

[1, 3]

Removals: 0

Start with the unsorted intervals.

Non-overlapping Intervals Solution


class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        
        intervals.sort(key=lambda x: x[1])
        
        last_end = intervals[0][1]
        removals = 0
        
        for i in range(1, len(intervals)):
            if intervals[i][0] < last_end:
                removals += 1
            else:
                last_end = intervals[i][1]
                
        return removals