Absorbing into the block you are building

Carry one open block through the pass, extend it when the next thing touches it, close it when it does not.

The same shape on a different input

Here it is on plain integers rather than intervals: compress a sorted list into runs of consecutive values.

1def compress_runs(values):2    if not values:3        return []4    blocks = [[values[0], values[0]]]5    for value in values[1:]:6        if value <= blocks[-1][1] + 1:        # touches or overlaps the open block7            blocks[-1][1] = max(blocks[-1][1], value)8        else:9            blocks.append([value, value])     # gap, so close and start fresh10    return blocks11 12print(compress_runs([1, 2, 3, 7, 8, 10]))13print(compress_runs([]))

Gotcha

Extend with a maximum, not an assignment

When a new interval connects, the block's end becomes the larger of the two ends, not simply the new one. An interval that sits entirely inside the open block would otherwise shrink it.

Sorting by start does not sort by end, so a fully contained interval is a normal occurrence rather than an edge case. This is the single most common bug in merging code and it only shows up on inputs where one interval swallows another.

1blocks = [[1, 10]]2incoming = [2, 4]                       # entirely inside the open block3 4blocks[-1][1] = incoming[1]             # wrong, the block shrinks to 45print(blocks)6 7blocks = [[1, 10]]8blocks[-1][1] = max(blocks[-1][1], incoming[1])   # right9print(blocks)

Code lab· 22 min

Absorb loops

Three questions answered by the same sweep. union_length returns the total length covered, counting overlapping parts once. count_blocks returns how many separate connected blocks the intervals form. largest_gap returns the widest uncovered stretch between two blocks. Answer all three in a single pass each, carrying only how far coverage currently reaches. Do not build a list of merged intervals.

solution.py

Tests

data = [[1, 3], [2, 6], [8, 10], [15, 18]]print(union_length(data), union_length([]), union_length([[1, 10], [2, 4]]))print(count_blocks(data), count_blocks([]), count_blocks([[1, 5]]))print(largest_gap(data), largest_gap([]), largest_gap([[1, 5]]))

Output

Run tests to see output.

Problem· 20 min

Merge Intervals

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

The same shape on a different input

Here it is on plain integers rather than intervals: compress a sorted list into runs of consecutive values.

1def compress_runs(values):2    if not values:3        return []4    blocks = [[values[0], values[0]]]5    for value in values[1:]:6        if value <= blocks[-1][1] + 1:        # touches or overlaps the open block7            blocks[-1][1] = max(blocks[-1][1], value)8        else:9            blocks.append([value, value])     # gap, so close and start fresh10    return blocks11 12print(compress_runs([1, 2, 3, 7, 8, 10]))13print(compress_runs([]))

data = [[1, 3], [2, 6], [8, 10], [15, 18]]print(union_length(data), union_length([]), union_length([[1, 10], [2, 4]]))print(count_blocks(data), count_blocks([]), count_blocks([[1, 5]]))print(largest_gap(data), largest_gap([]), largest_gap([[1, 5]]))