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 for a greedy approach. Sorting allows us to consider intervals in increasing order of their end times.

2. Iterate and Count: Initialize a variable count to 0 (representing the number of non-overlapping intervals) and lastEnd to negative infinity. Iterate through the sorted intervals:

   • If the current interval's start time is greater than or equal to lastEnd, it doesn't overlap with the previously selected non-overlapping intervals. Add it to the count, and update lastEnd to the current interval's end time.
   • Otherwise, the current interval overlaps. We don't add it to the count.

3. Calculate the number of removed intervals: The number of removed intervals is simply the total number of intervals minus the count of non-overlapping intervals.

Explanation

The greedy approach works because sorting by end time ensures that we prioritize intervals that finish earliest. By choosing intervals that end earliest first, we maximize the chances of fitting more non-overlapping intervals. If an interval overlaps with the previously selected interval, we discard it because it would reduce the space available for later intervals.

Code

function eraseOverlapIntervals(intervals: number[][]): number {
    if (intervals.length === 0) return 0;

    // Sort intervals by end time
    intervals.sort((a, b) => a[1] - b[1]);

    let count = 1; // Count of non-overlapping intervals
    let lastEnd = intervals[0][1]; // End time of the last non-overlapping interval

    for (let i = 1; i < intervals.length; i++) {
        const [start, end] = intervals[i];
        if (start >= lastEnd) {
            count++;
            lastEnd = end;
        }
    }

    return intervals.length - count; // Number of removed intervals
};

Complexity

• Time Complexity: O(N log N), dominated by the sorting step.
• Space Complexity: O(log N) or O(N), depending on the sorting implementation used. In-place sorting algorithms have O(log N) space complexity, while others might use O(N) extra space.