Merge Overlapping Bookings

Problem Statement

You're given a list of intervals, each with an integer start and end (start <= end) — think of each one as a booking on a shared resource, occupying every point from its start to its end. Some of these bookings overlap, or even just touch at a single point. Merge every group of overlapping or touching intervals into one interval that spans all of them, and print the resulting intervals, sorted by start, one per line.

Input Format

The input has n + 1 lines:

• Line 1: a single integer n, the number of intervals.
• The next n lines: each contains two integers, start and end, with start <= end.

Output Format

Print one line per merged interval, in ascending order of start, each line containing the merged interval's start and end separated by a single space.

Example Walkthrough

Take the first sample: intervals 9-12, 3-7, 14-20, 5-8, given in no particular order. Sorting them by start gives 3-7, 5-8, 9-12, 14-20. Start with 3-7 as the current merged interval. The next interval, 5-8, starts at 5, which is at or before the current interval's end (7), so it overlaps — extend the current interval's end to max(7, 8) = 8, making it 3-8. The next interval, 9-12, starts at 9, which is not at or before the current end (8), so it doesn't overlap — the current interval 3-8 is finished and gets recorded, and 9-12 becomes the new current interval. The last interval, 14-20, starts at 14, past the current end (12), so 9-12 is recorded as finished too, and 14-20 becomes current. With no more intervals left, 14-20 is recorded as the final one. The result: 3-8, 9-12, 14-20 — matching the expected output.

Approach

Comparing every interval to every other interval directly is possible but wasteful, and it's easy to miss chains of overlaps (interval A overlapping B, which overlaps C, even if A and C don't directly overlap). Sorting first turns this into a much simpler problem: once the intervals are ordered by start, any interval that's going to overlap with the interval currently being built up can only be the next one in sorted order, or a later one that still starts early enough — so a single left-to-right sweep, comparing only against the current merged interval, is enough to catch every overlap.

After sorting, keep a "current" interval, initialized to the first one. For each subsequent interval in sorted order, compare its start to the current interval's end. If the new interval's start is at or before that end, the two intervals overlap (or touch) — extend the current interval's end to whichever is larger, its own end or the new interval's end (the new interval's end isn't necessarily larger, since it could be entirely contained within the current interval). If instead the new interval's start comes strictly after the current interval's end, there's a gap: the current interval can't grow anymore, so add it to the result list and make the new interval the current one going forward. After the loop finishes, don't forget to add whatever interval is still "current" to the result — there's no later interval left to trigger that step naturally.

Sorting the intervals costs O(n log n), and the single sweep afterward that merges them touches each interval once, in O(n) — so the total time is dominated by the sort.

Common Mistakes

• Using strict < instead of <= when checking for overlap. The problem defines touching endpoints (like 7-11 and 11-14) as overlapping. A strict < check would treat them as non-overlapping and leave them as two separate intervals, 7-11 and 11-14, instead of merging them into 7-14.
• Extending the current interval's end to the new interval's end unconditionally. When an overlapping interval is entirely nested inside the current one — for example, current 1-10 followed by 2-3 — its end (3) is smaller than the current interval's end (10). Overwriting the current end with 3 would incorrectly shrink the merged interval; the end must be updated to the larger of the two.
• Forgetting to sort the intervals first. The single-pass merge only works because sorted intervals guarantee that anything still able to overlap the current interval appears next in the scan. Without sorting, an interval far later in the input could overlap an interval processed much earlier, and a simple one-pass sweep would miss that merge entirely.