A drone must inspect n patrol segments laid along a straight corridor. Segment i is the closed interval [low, high] (endpoints included). A single scan is fired at one position p and inspects every segment whose range contains p (that is, low <= p <= high). Two segments may be inspected by the same scan if some position lies in both. Report the minimum number of scans needed so that every segment is inspected by at least one scan.
Line 1: an integer n.
Next n lines: two integers low high (with low <= high).
A single integer: the minimum number of scans.
Example 1
Input
3 1 4 2 5 7 9
Expected
2
Explanation
One scan at position 4 covers [1,4] and [2,5]; a second scan at 9 covers [7,9]. Two scans suffice and one cannot cover all three.
Example 2
Input
3 1 2 3 4 5 6
Expected
3
Explanation
No position lies in two of these segments, so each needs its own scan: 3 scans.
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 →