A single shared lab bench receives n reservation requests. Request i asks to use the bench during the half-open time interval [s, e) with s < e. Two requests conflict if their intervals overlap; a request that ends exactly when another begins does NOT conflict (touching at an endpoint is allowed). You may accept any subset of requests as long as no two accepted requests conflict.
Determine the maximum number of requests that can be accepted.
Line 1: an integer n.
Next n lines: two integers s and e describing one request's half-open interval [s, e).
A single integer: the maximum number of mutually non-conflicting requests that can be accepted.
Example 1
Input
3 1 3 2 5 4 6
Expected
2
Explanation
Sort by end: [1,3), [2,5), [4,6). Accept [1,3); [2,5) starts at 2 < 3 so it conflicts and is skipped; [4,6) starts at 4 ≥ 3 so accept it. Two bookings.
Example 2
Input
1 0 10
Expected
1
Explanation
Only one request, so it is trivially accepted: the answer is 1.
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 →