0002MediumArraySorting

Pipeline Sensor Coverage

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A leak-detection crew has bolted acoustic sensors along a straight water pipeline. You are handed segments, where segments[i] = [start_i, end_i] records the stretch of pipe that sensor i can hear, measured in metres from the pumping station. A sensor whose two numbers are equal listens at a single point on the pipe.

Two stretches sit inside one monitored region whenever they share at least one point of pipe, and that includes the case where one stretch stops exactly where another picks up. Stretches that merely sit close together, with a gap of pipe between them however small, stay separate. Collapse the sensor list down to the fewest monitored regions that still cover precisely the same pipe, then return those regions arranged from the lowest starting metre to the highest.

The crew records sensors in whatever order the technicians walked the line, so segments arrives unordered.

Examples

Example 1

Input: segments = [[12, 18], [3, 7], [6, 9], [25, 25]]
Output: [[3, 9], [12, 18], [25, 25]]

The stretch 3..7 and the stretch 6..9 both hear metre 6, so they fold into 3..9. Nothing touches 12..18, and the point sensor at metre 25 stands on its own.

Example 2

Input: segments = [[40, 45], [45, 52]]
Output: [[40, 52]]

One stretch ends at metre 45 and the next begins there, so the shared mark joins them into a single region.

Example 3

Input: segments = [[100, 140], [110, 120]]
Output: [[100, 140]]

The shorter stretch sits wholly inside the longer one, which leaves the wider region unchanged.

Example 4

Input: segments = [[0, 0], [4, 4]]
Output: [[0, 0], [4, 4]]

Two point sensors with no metre mark in common stay separate, even though only three metres of pipe divide them.

Constraints

1 <= segments.length <= 10^4
segments[i].length == 2
0 <= start_i <= end_i <= 10^4

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def merge_coverage(segments: list[list[int]]) -> list[list[int]]:

Java

public int[][] mergeCoverage(int[][] segments)

The intended approach

Time O(n log n)Space O(n)

Sort the stretches by starting metre so that any stretch able to join the region under construction must be the next one seen. Then sweep once, extending the current region's far end whenever the next start falls at or before it, and opening a fresh region otherwise. Sorting is what makes the single comparison against the last region sufficient.

Pythonentry point: merge_coverage

def merge_coverage(segments):
    ordered = sorted(segments, key=lambda seg: (seg[0], seg[1]))
    regions = []
    for start, end in ordered:
        if regions and start <= regions[-1][1]:
            if end > regions[-1][1]:
                regions[-1][1] = end
        else:
            regions.append([start, end])
    return regions

The obvious version

Union-find over pairwise overlap, then span each component. Deliberately not sort-and-sweep, so it shares no logic with the reference.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_merge(segments):
    n = len(segments)
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for i in range(n):
        for j in range(i + 1, n):
            s1, e1 = segments[i]
            s2, e2 = segments[j]
            if s1 <= e2 and s2 <= e1:
                ra, rb = find(i), find(j)
                if ra != rb:
                    parent[rb] = ra

    groups = {}
    for i in range(n):
        groups.setdefault(find(i), []).append(segments[i])
    out = [[min(m[0] for m in g), max(m[1] for m in g)] for g in groups.values()]
    return sorted(out)

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in