Domain 2MediumCORE

Non-overlapping Intervals

We are given an array of time slots (intervals) defined by [start, end]. The objective is to remove the minimum number of these intervals so that no two remaining intervals overlap.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Greedy

435. Non-overlapping Intervals

Model: qwen3.5:9b
Topics: Greedy
FAANG asked: 1
Acceptance rate: 43.8%


Problem Breakdown

We are given an array of time slots (intervals) defined by [start, end]. The objective is to remove the minimum number of these intervals so that no two remaining intervals overlap.

Key constraints and definitions:

  • Overlap: Two intervals [a,b][a,b] and [c,d][c,d] overlap if they share any common point strictly inside their range (i.e., max⁡(a,c)<min⁡(b,d)\max(a,c) < \min(b,d)).
  • Touching is allowed: If one interval ends at 2 ([1,2]) and another starts at 2 ([2,3]), they do not overlap.
  • Goal Transformation: Minimizing the number of removed intervals is mathematically equivalent to maximizing the number of kept (non-overlapping) intervals. If we find KK non-overlapping intervals can be kept out of a total of NN, then the answer is simply N−KN - K.
  • Edge Cases: Empty input list, single interval, negative coordinates, and duplicate intervals all need to be handled naturally by our logic without special if blocks.

Intuition

If we try every possible combination of removals (brute force), that would involve checking subsets or dynamic programming which is too slow (O(2N)O(2^N)).

The key insight here comes from the Interval Scheduling Maximization problem pattern: To fit as many non-overlapping intervals as possible, we should prioritize picking intervals that finish earliest. Why? Because an interval ending earlier leaves more “room” for subsequent intervals to start without overlapping.

So, instead of sorting by start time (which might pick a long interval early and block others), we sort by end time. This greedy strategy ensures that whenever we have a choice between two compatible intervals, picking the one with the smallest end point is always optimal for future compatibility.

Approach

  1. Sort: Sort all intervals based on their end value in ascending order. If ends are equal, secondary sort by start doesn’t strictly matter but keeps consistency.
  2. Iterate & Count Kept: Initialize a counter for kept intervals (count) and track the end time of the last accepted interval (last_end).
  3. Greedy Selection: Loop through the sorted list:
    • If the current interval’s start is greater than or equal to last_end, it doesn’t overlap with our previous selection. We keep this interval, update last_end to the current end time, and increment count.
    • Otherwise (if there is an overlap), we implicitly “remove” this interval by skipping it in our count of kept intervals.
  4. Calculate Result: Return total number of intervals minus count.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N), dominated by the sorting step where NN is the number of intervals. The linear scan takes O(N)O(N).
  • Space Complexity: O(1)O(1) auxiliary space (excluding input storage), assuming an in-place sort or ignoring the stack overhead for Timsort which Python uses (O(log⁡N)O(\log N)).

Solution

def eraseOverlapIntervals(intervals):
    if not intervals:
        return 0
    
    # Sort by end time to prioritize finishing early (Greedy)
    intervals.sort(key=lambda x: x[1])
    
    kept_count = 0
    last_end = float('-inf')
    
    for start, end in intervals:
        if start >= last_end:
            # No overlap with the previously selected interval
            kept_count += 1
            last_end = end
    
    return len(intervals) - kept_count

Edge Cases Handled

  • Empty Input: Returns 0 immediately.
  • Single Interval: Loop runs once, keeps it (kept_count=1), returns 1−1=01-1=0.
  • Touching Intervals (e.g., [1,2], [2,3]): Since condition is start >= last_end, a start of 2 against an end of 2 passes the check. They are kept as non-overlapping.
  • Duplicate Intervals: If multiple identical intervals exist, only one will satisfy the last_end constraint (the first one encountered after sorting), and subsequent duplicates will be skipped/removed correctly.