Show problems as
Classic problem #56MediumArraySorting

Merge Intervals

Real-world version: Pipeline Sensor Coverage
Tracked in this browser only
Read Merge Intervals on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstMerge Intervals · Arrays, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def merge_coverage(segments: list[list[int]]) -> list[list[int]]:
Java
public int[][] mergeCoverage(int[][] segments)

More on the same topics