A city has n billboards. Billboard i is lit during the closed time interval [s, e] with s ≤ e. An inspector visits at chosen instants of time; billboard i is covered if at least one chosen instant t satisfies s ≤ t ≤ e (endpoints count as covered). You may choose any real-valued or integer instants.
Find the minimum number of inspection instants needed so that every billboard is covered by at least one instant.
Line 1: an integer n.
Next n lines: two integers s and e describing one billboard's closed lit interval [s, e].
A single integer: the minimum number of inspection instants required.
Example 1
Input
3 1 4 2 5 7 9
Expected
2
Explanation
Sort by end: [1,4], [2,5], [7,9]. Place an instant at 4 — it also covers [2,5]. Then [7,9] needs a new instant at 9. Two instants.
Example 2
Input
1 5 5
Expected
1
Explanation
One billboard lit at the single instant 5 needs exactly one inspection.
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 →