Engineering practice · 25 MIN

Merge overlapping reservations

Sort once, then maintain a compact frontier.

Order intervals by start time. The last merged interval is the only interval you need to compare with the next one. Closed intervals that touch at one endpoint merge in this contract. Copy input rows so the original reservations remain unchanged. Sorting dominates the running time.

Treat the function as a small service: define a contract, maintain an invariant, and test the boundaries.

Read the example

rows = [[5, 7], [1, 3]]
print(sorted(rows))

[[1, 3], [5, 7]]

Your challenge

Input is a list of [start,end] integer pairs with start <= end. Merge touching or overlapping closed intervals, sort ascending, and return a new list.

Solution cost: O(n log n) time · O(n) for sorting and output. space

Common trap

Setting the merged end to end without max breaks nested reservations.

Further reading: Python sorting HOWTO