Non-overlapping Intervals

GreedyIntervals

20 min

Problem Statement

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.

Example

Example 1:

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

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

Output: 1

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

Solution

The greedy approach is to sort the intervals by their end times. Then, we iterate through the sorted intervals and keep track of the end time of the last non-overlapping interval. If the current interval's start time is greater than or equal to the last end time, it's non-overlapping. Otherwise, we must remove it.

Algorithm Steps

Sort the intervals based on their end times.
Initialize `count` of non-overlapping intervals to 1 and `end` to the end time of the first interval.
Iterate through the rest of the intervals.
If the current interval's start time is greater than or equal to `end`, it's non-overlapping. Increment `count` and update `end`.
The minimum number of intervals to remove is `total_intervals - count`.

Non-overlapping Intervals

Greedy Approach

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

Output: 4

Progress1 / 1

Ready to start the visualization

Intervals

[1, 2]

[2, 3]

[3, 4]

[1, 3]

Non-overlapping Count

Last End Time

Non-overlapping Intervals Solution


class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key = lambda i : i[1])
        res = 0
        k = float('-inf')
        
        for x, y in intervals:
            if x >= k:
                k = y
            else:
                res += 1
        return res