A rancher lays n fence strips along a straight fence line. Each strip is a closed segment [start, end] (a strip with start == end is a single post). Two strips belong to the same block if they share at least one point — that is, they overlap or touch at an endpoint. Sharing is transitive: if strip A shares a point with B and B with C, then A, B and C form one block. Count the number of separate blocks.
Line 1: an integer n.
Next n lines: two integers start and end describing one strip.
A single integer: the number of separate blocks after joining.
Example 1
Input
4 1 3 2 5 7 9 8 10
Expected
2
Explanation
[1,3] and [2,5] overlap into one block [1,5]; [7,9] and [8,10] overlap into another [7,10]. Two blocks.
Example 2
Input
3 1 2 2 3 3 4
Expected
1
Explanation
Each strip touches the next at a shared endpoint, so all three chain into a single block [1,4].
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 →