Given an array of intervals, return the minimum number of intervals you must remove so that the remaining intervals do not overlap. Two intervals [a, b] and [c, d] do not overlap if c >= b or a >= d. Pattern focus: Interval Scheduling. Sort by end time and keep the interval that finishes earliest so that more intervals can be scheduled afterward.
intervals = list of [start, end] pairs
minimum number of removals
Example 1:
Input:
intervals = [[1,2],[2,3],[3,4],[1,3]]
Output:
1
Explanation:
Removing [1,3] leaves a fully non-overlapping set.
Example 2:
Input:
intervals = [[1,2],[1,2],[1,2]]
Output:
2
Explanation:
Only one interval can remain because all three overlap completely.
Example 3:
Input:
intervals = [[1,100],[11,22],[1,11],[2,12]]
Output:
2
Explanation:
Keeping short intervals after sorting by end time minimizes removals.