Non Overlapping Intervals

Problem Statement

You are given an array of intervals, where each interval is represented as an array of two integers, intervals[i] = [start_i, end_i]. Your task is to determine the minimum number of intervals you need to remove to ensure that the remaining intervals do not overlap.

Note: Intervals that only touch at a point are considered non-overlapping. For example, intervals [1, 2] and [2, 3] do not overlap.

Examples

Example 1:

Input: intervals = [
                    [1, 2],
                    [2, 3],
                    [3, 4],
                    [1, 3]
                   ]
Output: 1

Explanation:
The intervals [1,2], [2,3], and [3,4] can remain as they are non-overlapping.
The interval [1,3] overlaps with [1,2] and [2,3]. To make the remaining intervals non-overlapping, we can remove [1,3].

Example 2:

Input: intervals = [
                    [1, 2],
                    [1, 2],
                    [1, 2] 
                   ]
Output: 1

Explanation:
You need to remove two [1,2] to make the rest of the intervals non-overlapping.

To leave only one interval, we must remove 2 intervals.

Example 3:

Input: intervals = [
                    [1, 2],
                    [2, 3]
                   ]
Output: 0

Explanation:
The intervals [1,2] and [2,3] do not overlap (they touch at the endpoint).
No intervals need to be removed.

Different Approaches

1️⃣ Greedy Approach

Intuition:

The greedy approach works by sorting the intervals based on their end times. By always choosing the interval that ends the earliest, we can maximize the number of non-overlapping intervals.

Steps:

1. Sort the intervals by their end times.
2. Initialize a variable count to track the number of intervals to remove and lastEnd to keep track of the end of the last added non-overlapping interval.
3. Iterate through the sorted intervals:
   • If the current interval overlaps with the last added interval (i.e., its start time is less than the lastEnd), increment the count.
   • If it does not overlap, update lastEnd to the end time of the current interval.
4. Return the count as the minimum number of intervals to remove.

Dry Run:

intervals = [
             [1, 2],
             [2, 3],
             [3, 4],
             [1, 3]
            ]

Step 1: Sort the intervals based on end times:

intervals = [
             [1, 2],
             [2, 3],
             [1, 3],
             [3, 4]
            ]

Initialization:

intervals = [
             [1, 2],
             [2, 3],
             [1, 3],
             [3, 4]
            ]
count = 0
lastEnd = 2 (from the first interval [1, 2])

Iteration:

intervals = [
             [1, 2],
             [2, 3],
             [1, 3],
             [3, 4]
            ]
count = 0
lastEnd = 2 (from the first interval [1, 2])

i = 1 (interval [2, 3])
     current Interval Start Time < lastEnd
     2 < lastEnd (2)
     False // No overlap
     Update lastEnd = current interval's end time
     lastEnd = 3

i = 2 (interval [1, 3])
     current Interval Start Time < lastEnd
     1 < lastEnd (3)
     True // Overlap
     Increment count
          count = 1

i = 3 (interval [3, 4])
     current Interval Start Time < lastEnd
     3 < lastEnd (3)
     False // No Overlap
     Update lastEnd = current interval's end time.
     lastEnd = 4

Return

Return count = 1

Code:

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

using namespace std;

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

    int count = 0; // Count of intervals to remove
    int lastEnd = intervals[0][1]; // End time of the last added interval

    for (int i = 1; i < intervals.size(); ++i) {
        // If the current interval starts before the last one ends, we have an overlap
        if (intervals[i][0] < lastEnd) {
            count++; // Increase the count of removed intervals
        } else {
            lastEnd = intervals[i][1]; // Update the end time
        }
    }

    return count; // Return the count of removed intervals
}

int main() {
    vector<vector<int>> intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
    int result = eraseOverlapIntervals(intervals);
    cout << "Minimum number of intervals to remove: " << result << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n log n)
  • Sorting the interval takes O(n log n).
  • The single pass through the intervals takes O(n).
  • Overall Complexity: O(n log n).
• Space Complexity: O(1)