A broadcast console holds n booked advertising slots. Slot i occupies the half-open interval [start, end); two slots clash if their intervals overlap over a stretch of positive length (slots that only touch at an endpoint do not clash). Cancel as few slots as possible so that no two remaining slots clash.
Line 1: an integer n.
Next n lines: two integers start end (with start < end).
A single integer: the minimum number of slots that must be cancelled.
Example 1
Input
4 0 3 1 2 2 4 3 5
Expected
2
Explanation
Keeping [1,2) and [2,4) leaves two non-overlapping slots; the other two must go, so the minimum number of cancellations is 2.
Example 2
Input
3 0 1 1 2 2 3
Expected
0
Explanation
The three slots only touch at endpoints and never clash, so none need to be cancelled.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →