Standard Bar Greedy Approach · Medium O(n log n) · O(1)
A station received more program submissions than its day can hold; submissions are half-open time blocks that may overlap each other. Producers must pull the fewest submissions so the survivors never overlap. Ranking by earliest finish and keeping every submission that starts at or after the last kept finish does exactly that — everything culled is the minimum cut.
Input: A list of intervals [start, end].
Output: Return the minimum number of intervals to remove so the rest are pairwise non-overlapping.
1 <= intervals.length <= 10^5intervals[i].length == 2-5 * 10^4 <= start < end <= 5 * 10^4Input: {"intervals":[[1,2],[2,3],[3,4],[1,3]]}
Output: 1
Dropping [1,3] leaves the chain [1,2], [2,3], [3,4], where touching endpoints don't count as overlap.
Input: {"intervals":[[1,2],[1,2],[1,2]]}
Output: 2
Three identical blocks: two must go.