Merge a Day of Room Bookings: From Every Pair to One Sorted Pass

Comparing every booking with every other, round after round, rechecks pairs that cannot meet; sorting by start leaves only neighbours to compare.

Sorting bookings by start turns merging them from repeated rounds over every pair into one pass that compares each booking with one other. A meeting room's day holds five bookings, in the order they were made: 9 to 11, 14 to 16, 10 to 12, 18 to 19 and 15 to 17, written [9, 11] and so on. The task is the list of times the room is busy, with overlapping bookings merged into one.

The brute force merges any overlapping pair it finds and starts again, until a full round finds none. A round compares every pair, O(n²) for n bookings, and each merge removes one booking, so up to n rounds can run: O(n³) in the worst case. On these five it takes 3 rounds and 10 comparisons. The repeated work is that every round rechecks pairs far apart in time, such as [9, 11] and [18, 19], which could never overlap.

Merging until stable against one sorted pass

Until stableO(n²) per round, up to n rounds

Compare every pair; merge the first overlap found and start the round again. Stop when a whole round merges nothing.

Sorted passO(n log n) time

Sort by start, then compare each booking only with the last merged one: extend it on overlap, otherwise start a new one.

After sorting by start, a booking that does not reach the last merged one cannot reach any booking before it, so only neighbours need comparing. The run draws the sorted bookings and the merged day, then counts the comparisons each approach made.

text

sorted bookings
          9   11  13  15  17  19
[9, 11]   ======
[10, 12]    ======
[14, 16]            ======
[15, 17]              ======
[18, 19]                    ====
merged
          9   11  13  15  17  19
[9, 12]   ========
[14, 17]            ========
[18, 19]                    ====
repeat until stable: 3 rounds, 10 comparisons
sorted pass: 4 comparisons

The room is busy 9 to 12, 14 to 17 and 18 to 19. The sorted pass compared 4 times, once per booking after the first, against 10 for the brute force, and the gap widens fast: for 1,000 bookings a single round of pairs is about 5 × 10⁵ comparisons. The cost is O(n log n) for the sort plus O(n) for the pass, with O(n) space for the output.

← → move through sections and cards