Problem Description

You are given an array of intervals, where each interval is represented as a pair of integers [start, end]. Your task is to find the minimum number of intervals you need to remove from the array so that the remaining intervals do not overlap.

Two intervals [a, b] and [c, d] are said to overlap if a < d and c < b. The solution must ensure that no two intervals in the final array overlap. You should not reuse or split intervals; each interval can be removed or kept as a whole.

Constraints:

• 1 ≤ intervals.length ≤ 10⁵
• intervals[i].length == 2
• -5 * 10⁴ ≤ intervals[i][0] < intervals[i][1] ≤ 5 * 10⁴

Thought Process

At first glance, it might seem that we need to check every possible combination of intervals to find the set with no overlaps, but that would be computationally intensive. Brute-force approaches would involve checking all subsets, which is not feasible for large inputs.

To optimize, let's consider the nature of the problem: we want to keep as many non-overlapping intervals as possible (which is equivalent to removing as few as possible). This is similar to the classic "activity selection" problem, where the goal is to select the maximum number of non-overlapping activities.

The key insight is that if we always pick the interval that ends earliest, we leave the most "room" for future intervals, minimizing potential overlaps. This leads us to a greedy approach, which is both efficient and effective for this scenario.

Solution Approach

We use a greedy algorithm to solve the problem efficiently. Here's a step-by-step breakdown:

1. Sort the intervals by their end time:
   • This ensures that at every step, we consider the interval that finishes earliest. This leaves the maximum possible space for subsequent intervals, reducing the chance of overlap.
2. Initialize a variable to track the end of the last added interval:
   • Let's call it end, and set it to negative infinity initially.
3. Iterate through the sorted intervals:
   • For each interval, check if its start time is at least end (i.e., it doesn't overlap with the previously selected interval).
   • If it doesn't overlap, we can keep it and update end to this interval's end time.
   • If it does overlap, we need to remove this interval, so we increment a removal counter.
4. Return the count of removed intervals:
   • This will be the minimum number of intervals to remove to make the rest non-overlapping.

This approach ensures that we always keep the maximum number of non-overlapping intervals, and thus remove the minimum necessary.

Example Walkthrough

Let's consider the input: intervals = [[1,2],[2,3],[3,4],[1,3]]

1. Sort by end time: The sorted intervals are [[1,2],[2,3],[1,3],[3,4]]
2. Initialize: end = -∞, remove_count = 0
3. Iterate:
   • [1,2]: start (1) ≥ end (-∞), so keep it. Update end = 2.
   • [2,3]: start (2) ≥ end (2), so keep it. Update end = 3.
   • [1,3]: start (1) < end (3), so overlap. Increment remove_count = 1.
   • [3,4]: start (3) ≥ end (3), so keep it. Update end = 4.
4. Result: We removed 1 interval ([1,3]) to make the rest non-overlapping.

Time and Space Complexity

• Brute-force: Checking all subsets of intervals would be O(2ⁿ), which is not feasible for large n.
• Optimized (Greedy) Approach:
  • Sorting the intervals takes O(n log n).
  • The single pass through the intervals is O(n).
  • Thus, the total time complexity is O(n log n).
  • Space complexity is O(1) if sorting in-place, or O(n) if creating a new sorted array.

Summary

The Non-overlapping Intervals problem is elegantly solved using a greedy strategy: always keep the interval that ends earliest, and remove overlapping ones. This approach leverages sorting and a single linear scan, resulting in an efficient O(n log n) solution. The key insight is to minimize removals by maximizing the number of non-overlapping intervals, which aligns with the classic activity selection problem. This makes the solution both simple and powerful for large datasets.

Code Implementation

class Solution:
    def eraseOverlapIntervals(self, intervals):
        if not intervals:
            return 0
        # Sort intervals by end time
        intervals.sort(key=lambda x: x[1])
        end = float('-inf')
        remove_count = 0
        for interval in intervals:
            if interval[0] >= end:
                end = interval[1]
            else:
                remove_count += 1
        return remove_count
      

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        int end = INT_MIN, remove_count = 0;
        for (const auto& interval : intervals) {
            if (interval[0] >= end) {
                end = interval[1];
            } else {
                ++remove_count;
            }
        }
        return remove_count;
    }
};
      

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int end = Integer.MIN_VALUE, removeCount = 0;
        for (int[] interval : intervals) {
            if (interval[0] >= end) {
                end = interval[1];
            } else {
                removeCount++;
            }
        }
        return removeCount;
    }
}
      

var eraseOverlapIntervals = function(intervals) {
    if (!intervals.length) return 0;
    intervals.sort((a, b) => a[1] - b[1]);
    let end = -Infinity, removeCount = 0;
    for (let interval of intervals) {
        if (interval[0] >= end) {
            end = interval[1];
        } else {
            removeCount++;
        }
    }
    return removeCount;
};