Problem Description

You are given an array of intervals where each interval is represented as intervals[i] = [start_i, end_i]. Your task is to find the minimum number of intervals that need to be removed so that the remaining intervals do not overlap with each other.

Two intervals are considered non-overlapping if they only touch at a single point. For example, [1, 2] and [2, 3] are non-overlapping because they only share the boundary point 2, but [1, 3] and [2, 4] are overlapping because they share the range from 2 to 3.

The solution uses a greedy approach with sorting. First, the intervals are sorted by their ending points in ascending order. This ordering allows us to always keep the interval that ends earliest, maximizing the space available for subsequent intervals.

The algorithm works by:

1. Sorting intervals by their end times using intervals.sort(key=lambda x: x[1])
2. Tracking the end time of the last kept interval with variable pre (initialized to negative infinity)
3. Starting with ans = len(intervals) (assuming all intervals need to be removed initially)
4. For each interval [l, r]:
   • If the start time l is greater than or equal to pre (no overlap), we keep this interval by updating pre = r and decrementing ans by 1
   • Otherwise, there's an overlap and we skip this interval (it gets removed)

The final answer is the value of ans, representing the minimum number of intervals that must be removed to eliminate all overlaps.

Intuition

The key insight is that when we have overlapping intervals, we want to keep the interval that ends earliest and remove the others. Why? Because an interval that ends earlier leaves more room for future intervals to fit without overlapping.

Think of it like scheduling meetings in a conference room. If two meetings conflict, which one should we cancel? We should keep the meeting that ends first because it frees up the room sooner, allowing more meetings to potentially be scheduled afterward.

This leads us to a greedy strategy: sort intervals by their ending times. Then, as we go through the sorted list, we always keep the first interval we encounter. For subsequent intervals, we check if they start after the previous kept interval ends. If yes, we keep it; if no, we remove it.

Why does sorting by end time work better than sorting by start time? Consider intervals [1, 100] and [2, 3]. If we sort by start time and keep [1, 100] first, we'd have to remove many intervals that fall within this large range. But if we sort by end time and keep [2, 3] first, we only block a small time range, potentially allowing more intervals after time 3.

The counting logic is clever: instead of counting removals directly, we start with ans = len(intervals) (assuming all are removed) and subtract 1 each time we find an interval we can keep. This way, ans naturally becomes the count of removed intervals.

The variable pre tracks the end time of the last interval we decided to keep, starting at negative infinity to ensure the first interval is always kept. For each new interval [l, r], if l >= pre, there's no overlap with our previously kept interval, so we can keep this one too by updating pre = r.

Solution Approach

The implementation follows a greedy algorithm with sorting as the preprocessing step. Here's how the solution works step by step:

1. Sort the intervals by ending time:

intervals.sort(key=lambda x: x[1])

This sorts all intervals in ascending order based on their right boundary (end time). This ordering is crucial for the greedy strategy to work correctly.

2. Initialize tracking variables:

ans = len(intervals)
pre = -inf

• ans starts as the total number of intervals, assuming we need to remove all of them initially
• pre tracks the right boundary of the last interval we decided to keep, initialized to negative infinity to ensure the first interval can always be selected

3. Iterate through sorted intervals:

for l, r in intervals:
    if pre <= l:
        ans -= 1
        pre = r

For each interval [l, r]:

• Check if the current interval's left boundary l is greater than or equal to pre (the end of the last kept interval)
• If pre <= l, this means no overlap exists:
  • Decrement ans by 1 (one less interval needs to be removed)
  • Update pre = r to mark this interval as the new "last kept interval"
• If pre > l, there's an overlap, so we skip this interval (it gets removed) and don't update any variables

4. Return the result:

return ans

The final value of ans represents the minimum number of intervals that must be removed.

Time Complexity: O(n log n) where n is the number of intervals, dominated by the sorting step.

Space Complexity: O(1) if we don't count the space used by the sorting algorithm (typically O(log n) for the recursion stack in Python's Timsort).

The greedy choice of always keeping the interval with the earliest end time when there's no overlap is optimal because it maximizes the remaining time available for future intervals, minimizing the total number of removals needed.

Example Walkthrough

Let's walk through the algorithm with a concrete example to see how it works.

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

Step 1: Sort by ending points After sorting by the second element (end time):

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

Wait, let me re-sort correctly:

• [1,2] ends at 2
• [2,3] ends at 3
• [1,3] ends at 3
• [3,4] ends at 4

Sorted: [[1,2], [2,3], [1,3], [3,4]]

Step 2: Initialize variables

• ans = 4 (assume all 4 intervals need removal initially)
• pre = -∞ (no interval kept yet)

Step 3: Process each interval

Interval 1: [1,2]

• Check: Is 1 >= -∞? Yes!
• Keep this interval: ans = 4 - 1 = 3
• Update: pre = 2

Interval 2: [2,3]

• Check: Is 2 >= 2? Yes! (they touch at point 2, which is non-overlapping)
• Keep this interval: ans = 3 - 1 = 2
• Update: pre = 3

Interval 3: [1,3]

• Check: Is 1 >= 3? No! (1 < 3, so this overlaps with our last kept interval)
• Remove this interval: ans stays at 2
• No update to pre

Interval 4: [3,4]

• Check: Is 3 >= 3? Yes!
• Keep this interval: ans = 2 - 1 = 1
• Update: pre = 4

Result: ans = 1

We removed 1 interval ([1,3]) and kept three intervals: [1,2], [2,3], and [3,4]. These three intervals don't overlap - they only touch at boundary points, which is allowed.

The key insight: by sorting by end times and greedily keeping intervals that end earliest, we maximized the number of intervals we could keep, thus minimizing removals.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation intervals.sort(key=lambda x: x[1]), which sorts the intervals by their end points. Sorting n intervals takes O(n × log n) time. After sorting, the algorithm iterates through the sorted intervals once in O(n) time. Therefore, the overall time complexity is O(n × log n) + O(n) = O(n × log n).

Space Complexity: O(log n)

The space complexity comes from the sorting algorithm. Python's built-in sort() method uses Timsort, which requires O(log n) space in the worst case for its recursion stack. The rest of the algorithm uses only a constant amount of extra space for variables like ans and pre. Therefore, the overall space complexity is O(log n).

Common Pitfalls

1. Sorting by Start Time Instead of End Time

A common mistake is sorting intervals by their start time rather than end time. This seems intuitive but leads to suboptimal solutions.

Wrong approach:

intervals.sort(key=lambda x: x[0])  # Sorting by start time - INCORRECT!

Why it fails: Consider intervals [[1,100], [2,3], [3,4], [4,5]]. Sorting by start time keeps them in the same order. If we greedily keep the first interval [1,100], we must remove all others. However, the optimal solution is to remove only [1,100] and keep the rest.

Correct approach:

intervals.sort(key=lambda x: x[1])  # Sort by end time

This ensures we always keep intervals that end earliest, leaving maximum room for future intervals.

2. Incorrect Overlap Detection

Another pitfall is misunderstanding when intervals overlap. Remember that intervals touching at a single point are non-overlapping.

Wrong comparison:

if previous_end < start:  # INCORRECT - misses boundary case
    intervals_to_remove -= 1
    previous_end = end

Correct comparison:

if previous_end <= start:  # CORRECT - allows touching intervals
    intervals_to_remove -= 1
    previous_end = end

The difference is crucial: [1,2] and [2,3] should both be kept (they only touch at point 2), but using < instead of <= would incorrectly identify them as overlapping.

3. Initializing the Previous End Incorrectly

Some might initialize previous_end to 0 or the first interval's end, which can cause issues.

Wrong initialization:

previous_end = 0  # INCORRECT - assumes no negative intervals
# or
previous_end = intervals[0][1]  # INCORRECT - skips first interval check

Correct initialization:

previous_end = -inf  # or float('-inf')

Using negative infinity ensures the first interval is always considered non-overlapping and can be kept.

4. Counting Kept Intervals Instead of Removed Ones

The problem asks for intervals to remove, not keep. A common error is counting the wrong thing.

Wrong approach:

kept_count = 0
for start, end in intervals:
    if previous_end <= start:
        kept_count += 1  # Counting kept intervals
        previous_end = end
return kept_count  # WRONG - returns kept count, not removed count

Correct approach:

return len(intervals) - kept_count  # Convert to removed count
# OR start with total and decrement (as in the provided solution)