37. Non-overlapping Intervals
Remove as few intervals as possible so that the intervals left behind can coexist without overlap. You need the minimum removal count, not a list of removed intervals.
Because the intervals are half-open, one interval may start exactly when another ends. This differs from the closed-interval merging problems.
Example 1
Input
[[1,2],[2,3],[1,3]]
Output
1
Explanation: Keep [1,2) and [2,3), removing [1,3).
Example 2
Input
[[0,3],[3,6],[2,4]]
Output
1
Explanation: The two length-three intervals fit together; keeping the shortest interval [2,4) would lose both.
Constraints
0 <= intervals.length <= 105intervals[i].length == 2-231 <= start < end <= 231 - 1
Hints
Hint 1
Minimize removals by maximizing the kept occurrences.
Hint 2
Which first finish leaves the most room for every later choice?
Hint 3
Sort by end, keep each compatible interval, and subtract kept from n.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Earliest finish defeats shortest duration
[[0,3],[3,6],[2,4]]
1