Intervals
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.
Key idea
The loop
Sorted by start, the intervals arrive in the only order that matters. Carry one block that is still open. Each new interval either connects to it, in which case the block's end extends, or it does not, in which case the block is finished and a new one opens.
That is a three-line loop and it is the answer to a surprising number of problems.
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.
Tip
The `+ 1` is the touching decision again
For consecutive integers, 3 and 4 belong to the same run even though they are not equal, so the connection test is value <= end + 1. For intervals measured continuously there is no gap of one to close, and the test drops the + 1.
That single character is the same closed-versus-half-open decision from the last lesson, wearing different clothes. Ask what counts as adjacent before writing the comparison.
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.
Edge cases
The empty input
Opening the first block before the loop means an empty input has to be handled separately, or the indexing raises. The alternative is starting with no block at all and treating an empty block list as always needing a fresh one, which removes the special case at the cost of one extra condition in the loop.
Either is fine. Pick one deliberately rather than discovering the empty case from a failed test.
Cost
Where the time goes
The pass is O(n). The sort is O(n log n) and dominates, so the whole thing is O(n log n) time and O(n) space for the output.
Worth saying explicitly in an interview: the algorithm is linear and the sort is the expensive part. If the input arrives already sorted, which some problems promise, the whole thing is linear.
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.
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 the tests when you are ready.
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.