Given a list of closed intervals, return the minimum number of intervals to remove so that the rest are pairwise non-overlapping. Intervals that only touch — [1,2] and [2,3] — do not overlap.
Examples
Example 1:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: removing [1,3] leaves a clean chain.
Example 2:
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Example 3:
Input: intervals = [[1,2],[2,3]]
Output: 0
Example 4:
Input: intervals = [[1,100],[11,22],[1,11],[2,12]]
Output: 2
Constraints
1 <= intervals.length <= 10^5
intervals[i] is [start, end] with -5 * 10^4 <= start < end <= 5 * 10^4
Prerequisites
Sorting as a setup move — most interval problems are one sort away from a single sweep, and choosing whether to sort by START or by END is the decision that matters.
How to think about it
1. Keep the Most, Sorted by End Optimal
Intuition
Flip the question: removing the fewest is keeping the most, which is the classic activity-selection problem. Sort by END and greedily keep every interval that starts at or after the last kept end — the earliest-ending choice leaves the most room for what follows, so it is never worse. Sorting by start instead is the trap, and [1,100] is in the tests to punish it.
Algorithm
1. Sort by end time. 2. Keep an interval when it starts at or after the last kept end; update that end. 3. Removals are the total minus the kept count.