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 in ascending order. This ensures that we consider intervals with earlier end times first.

2. Initialize variables: We'll need a variable lastEnd to track the end time of the last non-overlapping interval and a variable removedCount to count the number of intervals removed.

3. Iterate through sorted intervals:

   • If the current interval's start time is greater than or equal to the lastEnd, it means this interval doesn't overlap with the previous non-overlapping interval. We update lastEnd to the current interval's end time.
   • Otherwise, the current interval overlaps. We increment removedCount.

4. Return the count: After iterating through all intervals, removedCount will hold the minimum number of intervals to remove.

Explanation

The algorithm is based on a greedy approach. By sorting the intervals by their end times, we prioritize selecting intervals that end earlier. This allows us to maximize the number of non-overlapping intervals we can keep. If an interval overlaps with the previously selected non-overlapping interval, it's removed to maintain non-overlapping condition. This strategy ensures we find the minimum number of intervals to remove because we are always trying to fit in as many non-overlapping intervals as possible.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.Length == 0) {
            return 0;
        }

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

        int lastEnd = intervals[0][1];
        int removedCount = 0;

        for (int i = 1; i < intervals.Length; i++) {
            if (intervals[i][0] < lastEnd) {
                removedCount++;
            } else {
                lastEnd = intervals[i][1];
            }
        }

        return removedCount;
    }
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step.
• Space Complexity: O(log N) or O(N), depending on the sorting algorithm used (in-place sorting like quicksort would be O(log N) while merge sort uses O(N) extra space). The rest of the algorithm uses constant extra space.