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 and Explanation

The core idea is to sort the intervals by their end times. After sorting, we iteratively check if the current interval overlaps with the previously selected non-overlapping interval. If it overlaps, we need to remove one of them. Since we've sorted by end time, it's always better to keep the interval with the earlier end time (because it leaves more room for subsequent non-overlapping intervals). If it doesn't overlap, we add it to our set of non-overlapping intervals.

1. Sort: Sort the intervals array by the end times of each interval. We can use a custom comparator for this.

2. Initialize: Create an array last to keep track of the latest non-overlapping interval we've selected. Initialize it to the first interval after sorting (since it's automatically non-overlapping with nothing). Also, initialize removedCount to zero.

3. Iterate: Iterate through the sorted intervals starting from the second interval.

4. Check for Overlap: For each interval, check if it overlaps with the last interval. An overlap occurs if the current interval's start time is less than or equal to the last interval's end time.

5. Handle Overlap: If an overlap occurs, increment removedCount (we're removing one interval) and proceed to the next interval. If there is no overlap, update last to the current interval.

6. Return: After iterating through all intervals, removedCount will represent the minimum number of intervals that need to be removed.

Code (Java)

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // Sort intervals by end time
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));

        int removedCount = 0;
        int[] last = intervals[0]; // Initialize with the first interval

        for (int i = 1; i < intervals.length; i++) {
            int[] current = intervals[i];
            if (current[0] < last[1]) { // Overlap
                removedCount++;
            } else {
                last = current; // Update last to current
            }
        }

        return removedCount;
    }
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step.
• Space Complexity: O(1) (excluding the input array). We use a constant amount of extra space.