Each entry of intervals is a pair [startᵢ, endᵢ] describing a stretch of the number line. Two intervals overlap when they share more than a single point. Intervals that only touch, such as [2,5] and [5,8], do not overlap.
Return the fewest intervals you must delete so that no two of the remaining ones overlap.
At most two of these can stay together, for example [2,3] and [3,6], which only touch at 3. So two intervals have to go.
[0,10] overlaps all three short intervals, and they don't overlap each other. Deleting just [0,10] is enough.
Neighbours only touch at -1 and 2, so nothing needs deleting.
Constraints
1 <= intervals.length <= 10⁵intervals[i].length == 2-5 · 10⁴ <= startᵢ < endᵢ <= 5 · 10⁴Deleting the fewest is the same as keeping the most. Among intervals that compete, the one that ends earliest leaves the most room for the rest.
Deleting the fewest intervals is the same as keeping the most. If at most k of the n intervals can stay together, the answer is n - k. So the real question is: how many intervals can you pick so that no two of them overlap?
Time O(n log n)Space O(1)
The full walkthrough and code are part of Premium
2