Combine overlapping bookings into blocks

Greedy choices and intervals Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
blocks: list[list[int]] = []
for s, e in sorted([[1, 10], [2, 3], [4, 12]]):
    if blocks and s <= blocks[-1][1]:
        blocks[-1][1] = e
    else:
        blocks.append([s, e])
print(blocks)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [[1, 3], [4, 12]]

Right: [2, 3] overwrote the block's end with 3, so [4, 12] no longer looked like an overlap.

Using max() for the new end stops a short booking from cutting a longer block, and then the answer becomes one block.

Why not the others?
  • B [[1, 12]]. That is what a correct merge returns; this version lost the end of [1, 10] at the second booking.
  • C [[1, 10], [4, 12]]. After [2, 3] the block's end is 3, not 10.
Bookings drawn as bars on one time axis, taken in start order and merged into blocks, with each step noting whether the booking extends a block or starts a new one, for two sets.

Steps come from running the Python solution.

Text version

Five bookings:

Intervals in input order: [1, 3], [8, 10], [2, 6], [9, 12], [15, 18].

  1. Take [1, 3]; merged [1, 3]. [1, 3] starts a new block
  2. Take [2, 6]; merged [1, 6]. [2, 6] overlaps: extend to 6
  3. Take [8, 10]; merged [1, 6], [8, 10]. [8, 10] starts a new block
  4. Take [9, 12]; merged [1, 6], [8, 12]. [9, 12] overlaps: extend to 12
  5. Take [15, 18]; merged [1, 6], [8, 12], [15, 18]. [15, 18] starts a new block

Result: [[1, 6], [8, 12], [15, 18]]

Four bookings that touch:

Intervals in input order: [5, 7], [1, 2], [2, 4], [7, 9].

  1. Take [1, 2]; merged [1, 2]. [1, 2] starts a new block
  2. Take [2, 4]; merged [1, 4]. [2, 4] overlaps: extend to 4
  3. Take [5, 7]; merged [1, 4], [5, 7]. [5, 7] starts a new block
  4. Take [7, 9]; merged [1, 4], [5, 9]. [7, 9] overlaps: extend to 9

Result: [[1, 4], [5, 9]]

30-second answer

Sort by start. Walk through the bookings keeping the list of blocks; if a booking starts at or before the last block's end, extend that block's end; otherwise start a new block. Sorting costs O(n log n) and the walk O(n); the sorted copy and the blocks take O(n) space.

Practise saying it · 45 s. No recording, just a timer

Explain combining overlapping bookings.

Say your answer out loud, then check which of these points you covered:

  • Sort by start
  • Extend with max end
  • O(n log n)

Deep dive

This is the merge intervals template: sort by start, then one pass.

Extend with max(end), because a long earlier booking can swallow later ones.

Decide whether touching counts as overlapping; here it does.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def merge_bookings(bookings: list[list[int]]) -> list[list[int]]:
    blocks: list[list[int]] = []
    for start, end in sorted(bookings):
        if blocks and start <= blocks[-1][1]:  # touches the last block
            blocks[-1][1] = max(blocks[-1][1], end)
        else:
            blocks.append([start, end])
    return blocks

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun mergeBookings(bookings: List<List<Int>>): List<List<Int>> {
    val blocks = mutableListOf<MutableList<Int>>()
    for (b in bookings.sortedWith(compareBy({ it[0] }, { it[1] }))) {
        val last = blocks.lastOrNull()
        if (last != null && b[0] <= last[1]) { // touches the last block
            last[1] = maxOf(last[1], b[1])
        } else {
            blocks.add(mutableListOf(b[0], b[1]))
        }
    }
    return blocks
}

Common mistakes

  • Setting the end to the new booking's end instead of the max.
  • Forgetting to sort first.

Senior take & follow-ups

Say the touching rule out loud before you code.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you add one new booking to an already merged list?

    Show hint

    Copy the blocks before it, merge everything that overlaps it, then copy the rest: O(n).

  2. What if bookings arrive one by one?

    Show hint

    Keep blocks in a balanced tree or sorted list keyed by start, and merge with the neighbours.

What each operation costs: Merge Sort · Quick Sort

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.