Non-overlapping Intervals and the End Time Greedy

"Non-overlapping Intervals" is a Medium-level staple in Meta, Amazon, Bloomberg loops, and it is a textbook fit for the Merge Intervals pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 3 of 11 in the Merge Intervals arc.

The Problem

Given intervals, return the minimum number to remove so the rest are mutually non-overlapping. Touching intervals do not overlap here. This is the interval version of activity selection — the one greedy proof every candidate should be able to sketch.

Input:  intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Remove [1, 3]; the rest are disjoint.

Recognizing the Merge Intervals Pattern

Interval problems — scheduling, calendars, resource booking — almost all reduce to one move: sort by start (or end), then sweep once while comparing each interval against a running boundary. Overlap exists when the next start is at most the current end. Sort plus linear sweep, O(n log n), is the backbone of the entire family.

Minimize removals equals maximize kept intervals — a scheduling maximization. The classic result: sorting by end time and always keeping the earliest-ending compatible interval is optimal, because an earlier end leaves no less room for the future than any alternative.

The Approach

Sort by end. Track the end of the last kept interval. For each interval, keep it if its start is at least the tracked end; otherwise count a removal. The exchange argument — any optimal solution can swap its first pick for the earliest-ending one without loss — justifies the greed in two sentences.

Sorting by start and greedily dropping the longer of any overlapping pair also works, but the end-time version is cleaner to defend under questioning.

Python Solution

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    """Minimum removals to make all intervals pairwise disjoint."""
    if not intervals:
        return 0
    intervals.sort(key=lambda iv: iv[1])       # earliest end first
    removals = 0
    last_end = intervals[0][1]
    for start, end in intervals[1:]:
        if start >= last_end:
            last_end = end                     # compatible: keep
        else:
            removals += 1                      # overlap: drop this one
    return removals

Complexity

• Time: O(n log n) — sort, then linear sweep
• Space: O(1) — a counter and one boundary value beyond the in-place sort

Interview Tips and Follow-Ups

• Rehearse the exchange argument aloud — 'why sort by end?' is guaranteed, and hand-waving it downgrades an otherwise perfect answer.
• Touching intervals ([1, 2], [2, 3]) are compatible here but merged in Merge Intervals — comparing the two conventions shows command of the family.
• Identical siblings: Minimum Arrows (later in this arc) and Activity Selection — one greedy, three phrasings.

That wraps part 3 of the Merge Intervals arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.