Non-overlapping Intervals

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

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.
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

• Invariant: the selected intervals are non-overlapping and end as early as possible.
• Sorting establishes a consistent processing order.
• Merge/greedy steps maintain a correct partial solution.
• After processing all intervals, the result is optimal and complete.

Trace (hand walkthrough)

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

Remove [1,3].

Walk:
- sort by end: [1,2],[2,3],[1,3],[3,4]
- take [1,2], take [2,3], skip [1,3] (overlaps), 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).

Complexity

• Time: O(n log n)
• Extra space: O(n) for sorting.

Implementation notes (Go)

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