Return the minimum number of intervals to remove so that the remaining intervals don't overlap. Intervals that only touch, such as [1, 2] and [2, 3], don't overlap.
Before you code
Removing as few as possible is keeping as many as possible: interval scheduling.
Hints
- Sort by end.
- Keep an interval when its start is at least the last kept end; otherwise count it as removed.
- O(n log n).
Production & complexity notes
When solving Non-overlapping intervals on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Scheduling and intervals to reinforce the underlying pattern.
What it practices
The earliest-end greedy, from Scheduling and intervals.