A telecom crew has already buried n separate fiber-optic cable segments along a single straight utility trench, each described by the meter marks where it begins and ends. The segments are listed in order of increasing start position, and no two of them touch or overlap, so right now the trench holds exactly n separate connected clusters of cable.
The crew has one more spool of cable, of a fixed length k, that they can splice into the trench as a brand-new segment [x, x + k] for any integer x of their choosing -- x may be negative, may land inside an already-clustered stretch with no benefit, or may bridge across an empty gap between two existing segments. Two segments (original or newly spliced) belong to the same cluster whenever their ranges overlap or merely touch at a single point, and this connectivity is transitive: if segment A shares a cluster with B, and B shares a cluster with C, then A, B, and C all belong to one cluster.
Decide where to splice the new segment so that, after splicing, the trench contains as few distinct connected clusters as possible, and report that minimum number of clusters.
Print a single integer: the minimum possible number of connected clusters after splicing in exactly one new segment of length k.
Example 1
Input
3 3 1 2 5 6 10 12
Expected
2
Explanation
The three segments start as 3 separate clusters. Splicing in the new length-3 segment as [2, 5] touches the first segment at 2 and touches the second segment at 5, merging them into one cluster; the third segment [10, 12] stays on its own since it cannot be reached as well. That leaves 2 clusters total, which is the minimum possible.
Example 2
Input
2 9 0 1 10 11
Expected
1
Explanation
The gap between the two segments runs from 1 to 10, a span of 9, exactly matching k. Splicing in [1, 10] touches both existing segments, merging everything into a single cluster, so 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 →