Non-overlapping Intervals

Given a list of intervals, return the minimum number of intervals to remove so that the remaining intervals are non-overlapping.

Why this is worth learning

Maximizing the number retained is equivalent to minimizing removals. Keep the earliest-finishing compatible interval because it leaves the largest future opportunity.

Before coding: one-minute experiment

How many intervals must be removed from [[1,2],[2,3],[1,3]]?

Function signature

func EraseOverlapIntervals(intervals [][]int) int

Inputs / outputs

• intervals: list of [start, end].
• Return: minimum number of intervals to remove.

Example

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

Remove [1,3].

Constraints

• 0 <= len(intervals) <= 100_000
• -1_000_000_000 <= start <= end <= 1_000_000_000

Core idea (near-solution)

This is equivalent to selecting the maximum number of non-overlapping intervals. Sort by end time and greedily keep intervals with the earliest end.

Invariant: the selected intervals are non-overlapping and end as early as possible.

Algorithm (step-by-step)

1. Sort intervals by end ascending, breaking equal ends by start ascending. This matters for the allowed point intervals: [1,2] must precede [2,2], so both can be retained.
2. Initialize count = 0 (kept), and end = -inf.
3. For each interval:
   • If start >= end, keep it and update end = interval.end.
   • Else, it overlaps; increment removals.
4. Return the number of removals.

Correctness sketch

Among intervals available after the last chosen end, take one with the earliest end. Any optimal remaining schedule has a first interval whose end is no earlier. Replacing that first interval with the greedy choice cannot block any later interval, because the replacement frees the timeline at least as early. Thus some optimal schedule starts with the greedy choice. Repeating the exchange argument on the remaining compatible intervals proves the maximum retained count. Subtracting this count from n gives minimum removals. Compatibility here permits a next start equal to the previous end, unlike closed-interval merging.

Trace (hand walkthrough)

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

Remove [1,3].

Walk:
- sort by (end,start): [1,2],[1,3],[2,3],[3,4]
- take [1,2], skip [1,3] (overlaps), take [2,3], take [3,4]
- removed count = 1

Pitfalls to avoid

• Sorting by start instead of end (breaks greedy optimality).
• Using > instead of >= for boundary touching (touching is allowed).

Debugging lens

Include equal finish times, nested intervals, touching intervals, and allowed zero-length intervals. A start-sorted greedy choice can retain a long interval that blocks several short ones.

Complexity

Time: O(n log n) for sorting plus O(n) scan. Auxiliary space: O(log n) sorting stack for the supplied in-place comparison sort, plus O(1) greedy state; no O(n) copy is made.

Implementation notes (Go)

• Sort by end time and keep the earliest finishing intervals.
• Removals = total - kept.

Contract precision

This task treats start>=previousEnd as compatible, so touching endpoints may both be retained. The reference sorts the outer input slice by end, then start. The stated start<=end bound includes zero-length intervals, which follow the same compatibility rule.

Reconstruction checkpoint

How many intervals must be removed from [[1,2],[2,3],[1,3]]?

Return to Intervals · Module quiz