Non-overlapping Intervals medium

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 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 intervals non-overlapping.

Steps

1. Sort the intervals: Sort the intervals by their end times. This is crucial because we prioritize intervals that end earlier to maximize the chance of including more intervals without overlaps.

2. Iterate and count: Initialize a variable last_end to keep track of the end time of the last non-overlapping interval. Iterate through the sorted intervals. If the current interval's start time is greater than or equal to last_end, it means this interval doesn't overlap with the previous ones, so we update last_end with its end time. Otherwise, the interval overlaps, and we increment a counter to keep track of the number of overlapping intervals we need to remove.

3. Return the count: The final count represents the minimum number of intervals to remove.

Explanation

The key idea is to greedily select intervals that end as early as possible. By sorting the intervals by their end times, we ensure that we always consider intervals that leave more room for subsequent non-overlapping intervals. If an interval overlaps with the previously selected non-overlapping interval, we remove it because choosing it would prevent us from selecting other potentially non-overlapping intervals later. This greedy approach leads to the optimal solution.

Code

def eraseOverlapIntervals(intervals):
    """
    Finds the minimum number of intervals to remove to make the rest non-overlapping.

    Args:
        intervals: A list of lists, where each inner list represents an interval [start, end].

    Returns:
        The minimum number of intervals to remove.
    """

    if not intervals:
        return 0

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

    last_end = intervals[0][1]  # End time of the last non-overlapping interval
    removed_count = 0

    for i in range(1, len(intervals)):
        start = intervals[i][0]
        end = intervals[i][1]

        if start < last_end:  # Overlap detected
            removed_count += 1
        else:
            last_end = end  # Update last_end if no overlap

    return removed_count

Complexity

• Time Complexity: O(N log N), dominated by the sorting step.
• Space Complexity: O(1) (in-place sorting; we only use a few extra variables).