353. Non-overlapping Intervals
You are given an array intervals, where intervals[i] = [start_i, end_i] describes a half-open stretch of the number line. Return the minimum number of intervals you must delete so that the ones left behind never overlap.
Two intervals that merely touch do not overlap: [1, 2] and [2, 3] can coexist, because the first one ends exactly where the second begins.
The answer is a single count — you never have to say which intervals to delete, only how few deletions suffice.
Example 1:
Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Explanation: [1, 3] overlaps both [1, 2] and [2, 3]. Deleting it leaves [1, 2], [2, 3], [3, 4], which only touch at endpoints.
Example 2:
Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2
Explanation: Three identical copies of [1, 2] all overlap each other, so only one copy may survive — two deletions.
Example 3:
Input: intervals = [[1, 2], [2, 3]]
Output: 0
Explanation: Touching at a single point is not an overlap, so nothing needs to be deleted.
Constraints:
- 1 ≤ intervals.length ≤ 10⁵
- -5 * 10⁴ ≤ start_i < end_i ≤ 5 * 10⁴
Hints:
Flip the question: deleting the fewest intervals is exactly the same as keeping the most. So ask instead — what is the largest set of mutually non-overlapping intervals?
Sort by end. The interval that finishes earliest leaves the most room for everything after it, so it is always safe to keep. Then greedily keep each next interval whose start is >= the end of the last one you kept; the answer is n minus the number kept.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Expected output: 1