There are n events. Event i runs from day start to day end inclusive, and you may attend it on any single day within [start, end]. You can attend at most one event per day, and each event can be attended at most once. Report the maximum number of events you can attend.
Line 1: an integer n.
Next n lines: two integers start end (with start <= end).
A single integer: the maximum number of events you can attend.
Example 1
Input
3 1 2 2 3 3 4
Expected
3
Explanation
Attend the first event on day 1, the second on day 2, and the third on day 3, so all 3 events fit.
Example 2
Input
3 1 1 1 1 1 1
Expected
1
Explanation
All three events can only be attended on day 1, but you attend one event per day, so at most 1 is possible.
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 →