A warehouse must confirm n delivery windows. Window i is the closed range [start_i, end_i] (both endpoints included). A single audit checkpoint scheduled at time t confirms every window whose range contains t. Find the minimum number of checkpoint times needed so that every one of the n windows contains at least one checkpoint.
Line 1: an integer n.
Next n lines: two integers start_i end_i describing window i (start_i <= end_i).
A single integer: the minimum number of checkpoints needed.
Example 1
Input
3 1 3 2 5 6 8
Expected
2
Explanation
A checkpoint at time 2 covers both [1,3] and [2,5]; a second checkpoint at time 6 covers [6,8]. Minimum is 2.
Example 2
Input
2 0 10 2 3
Expected
1
Explanation
A single checkpoint at time 2 (or anywhere in [2,3]) lies inside both windows, so 1 checkpoint suffices.
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 →