Non-Overlapping Intervals

Difficulty: Medium Source: NeetCode

Problem

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1,2] and [2,3] are non-overlapping.

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

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

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

Constraints:

• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• -5 * 10^4 <= start_i < end_i <= 5 * 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy algorithms — the classic interval scheduling maximization problem
• Sorting — sorting intervals by end time to make the greedy choice easy
• Intervals — understanding when two intervals overlap

1. Brute Force

Intuition

Try removing every possible subset of intervals and check if the remainder is non-overlapping. Return the size of the smallest subset that achieves this. This is exponential and only works on tiny inputs, but it proves the answer by exhaustive search.

Algorithm

1. For every subset of intervals (via bitmask):
   • Check if removing that subset leaves a non-overlapping set.
   • Track the minimum subset size that works.
2. Return the minimum.

Solution

def erase_overlap_intervals_brute(intervals):
    n = len(intervals)

    def is_non_overlapping(keep_mask):
        kept = [intervals[i] for i in range(n) if keep_mask & (1 << i)]
        kept.sort()
        for i in range(1, len(kept)):
            if kept[i][0] < kept[i-1][1]:
                return False
        return True

    min_remove = n
    for mask in range(1 << n):
        removed = bin(mask).count('1')
        if removed < min_remove and is_non_overlapping(mask ^ ((1 << n) - 1)):
            min_remove = removed
    return min_remove


print(erase_overlap_intervals_brute([[1,2],[2,3],[3,4],[1,3]]))  # 1
print(erase_overlap_intervals_brute([[1,2],[1,2],[1,2]]))        # 2
print(erase_overlap_intervals_brute([[1,2],[2,3]]))              # 0

Complexity

• Time: O(2^n * n) — exponential; only feasible for n ≤ ~20
• Space: O(n)

2. Greedy — Interval Scheduling Maximization

Intuition

The key insight is that minimizing removals is the same as maximizing the number of intervals we keep. This is the classic interval scheduling problem: sort by end time and greedily keep each interval that does not overlap the last kept one. By always picking the interval that ends earliest, we leave as much room as possible for future intervals — this is provably optimal.

The answer is then total intervals - max intervals we can keep.

Algorithm

1. Sort intervals by end time.
2. Initialize keep = 1 (always keep the first interval) and last_end = intervals[0][1].
3. For each subsequent interval [start, end]:
   • If start >= last_end (no overlap), keep it: increment keep, update last_end = end.
4. Return len(intervals) - keep.

Solution

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

    keep = 1
    last_end = intervals[0][1]

    for start, end in intervals[1:]:
        if start >= last_end:
            # No overlap with last kept interval — keep this one
            keep += 1
            last_end = end
        # Otherwise skip (remove) this interval

    return len(intervals) - keep


print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1
print(erase_overlap_intervals([[1,2],[1,2],[1,2]]))        # 2
print(erase_overlap_intervals([[1,2],[2,3]]))              # 0
print(erase_overlap_intervals([[-100,-87],[-99,-44],[-98,-19],[-97,7]]))  # 1

Complexity

• Time: O(n log n) — sorting dominates; the greedy sweep is O(n)
• Space: O(1) — only a few variables beyond the sort

Common Pitfalls

Sorting by start time instead of end time. Sorting by start gives the wrong greedy choice. The classic result says you must sort by end time to maximise the number of non-overlapping intervals kept.

Using strict less-than for the overlap check. Intervals that only touch at a point ([1,2] and [2,3]) are considered non-overlapping by this problem. Use start >= last_end (not >), so touching intervals are kept.

Returning keep instead of len(intervals) - keep. The question asks for the count of removals, not the count of intervals kept. Subtract from total.