Non-overlapping Intervals (LeetCode 435)

LC 435 — Problem

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Intervals 12 and 23 are considered non-overlapping (they only touch at a single point).

Input: intervals = 12,23,34,13

Output: 1

Explanation: 13 can be removed and the rest are non-overlapping.

Input: intervals = 12,12,12

Output: 2

Constraints: 1 ≤ intervals.length ≤ 10⁵ · intervals[i].length == 2 · -5 × 10⁴ ≤ startᵢ < endᵢ ≤ 5 × 10⁴

You have 4 intervals: 1100,23,45,67. Your task: remove the fewest intervals so that no two overlap. The natural first instinct — sort by start time, then greedily keep non-overlapping intervals.

FIG. 1 — SORTED BY START

[1,100]

[2,3]

[4,5]

[6,7]

— Sorted by start time —

The greedy rule: keep the first interval, then skip anything that overlaps with it. Look at the timeline above. How many intervals survive?