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 the greedy approach. Sorting ensures that we consider intervals with earlier end times first, maximizing the chance of including them without overlaps.

2. Greedy Approach: Iterate through the sorted intervals. Keep track of the last non-overlapping interval's end time (lastEndTime). For each interval, if its start time is greater than or equal to lastEndTime, it means it doesn't overlap with the previous interval, so we include it and update lastEndTime. Otherwise, it overlaps, and we increment the count of removed intervals.

3. Return the count: The final count of removed intervals is the minimum number needed to make the intervals non-overlapping.

Explanation

The greedy approach works because sorting by end times prioritizes intervals that finish earlier. By selecting intervals that finish earliest, we maximize the space for subsequent non-overlapping intervals. If an interval overlaps, it's better to remove it because keeping it would likely force us to remove more intervals later.

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty()) return 0;

    // Sort intervals by end time
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });

    int removedCount = 0;
    int lastEndTime = intervals[0][1]; // Initialize with the end time of the first interval

    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] < lastEndTime) { // Overlap detected
            removedCount++;
        } else {
            lastEndTime = intervals[i][1]; // Update lastEndTime for non-overlapping interval
        }
    }

    return removedCount;
}

int main() {
    vector<vector<int>> intervals1 = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
    cout << "Minimum intervals to remove (Example 1): " << eraseOverlapIntervals(intervals1) << endl; // Output: 1

    vector<vector<int>> intervals2 = {{1, 2}, {1, 2}, {1, 2}};
    cout << "Minimum intervals to remove (Example 2): " << eraseOverlapIntervals(intervals2) << endl; // Output: 2

    vector<vector<int>> intervals3 = {{1,100},{11,22},{1,11},{2,12}};
    cout << "Minimum intervals to remove (Example 3): " << eraseOverlapIntervals(intervals3) << endl; //Output 2


    return 0;
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step.
• Space Complexity: O(log N) in the best case (in-place sorting) or O(N) in the worst case (depending on the sorting algorithm used). The extra space used by lastEndTime and removedCount is constant.