Merge intervals: preserve the covered set

Sort so only one unresolved boundary remains

A baseline repeatedly finds an overlapping or touching pair and replaces it with its union until none remain. It is correct but awkward to order, and a naive full rescan after each merge can take O(n³) time. Sorting by start gives a simpler baseline improvement: all future starts are at least the current start, so only the last output interval can still grow.

After a processed prefix, output is sorted, represents exactly its covered set, and has strict gaps between intervals. If the next start is greater than the last end, it cannot meet any earlier output interval either, so append. Otherwise extend the last end to the maximum of both ends. The maximum matters for nesting: merging [1, 10) with [2, 3) must not shrink covered time. Earlier output intervals remain final because future starts cannot move backward across a gap.

Half-open means the start is included and end excluded. [1, 3) and [3, 6) do not overlap, yet their union is exactly [1, 6) with no gap, so the explicit touching policy permits merging. Sorting a copy plus scanning costs O(n log n) time and O(n) auxiliary space in Python, with O(n) possible output. Claiming O(1) space would ignore the sorted copy and sorting workspace. No event values are mutated, and new tuples prevent output edits from changing input pairs.

Follow-up 1: preserve separate touching reservations

Predict the one comparison that changes. Merge only when start < previous_end, so an endpoint equality starts a new result. The covered set is unchanged but the grouping policy now communicates reservation boundaries.

If preserving every event identity matters, merged ranges alone are insufficient; attach provenance or return a separate mapping. “Same covered time” is weaker than “same booking information.”

Follow-up 2: intervals arrive in arbitrary order forever

A balanced ordered index avoids sorting the entire collection on each arrival; an insertion must still inspect every interval it absorbs. A senior candidate states endpoint policy and proves why only the last sorted result is mutable. A lead candidate defines concurrent update ownership, provenance, and whether deleting one original booking must reconstruct previously merged coverage.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/09-merge-intervals
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def _intervals(intervals):
    if not isinstance(intervals, (list, tuple)):
        raise ValueError("expected a list or tuple of intervals")
    for pair in intervals:
        if (not isinstance(pair, (list, tuple)) or len(pair) != 2
                or any(type(x) is not int for x in pair) or pair[0] >= pair[1]):
            raise ValueError("intervals require integer start < end")

def merge_intervals(intervals):
    _intervals(intervals)
    result = []
    for start, end in sorted(intervals, key=lambda pair: (pair[0], pair[1])):
        if result and start <= result[-1][1]:
            result[-1] = (result[-1][0], max(result[-1][1], end))
        else:
            result.append((start, end))
    return result

import random
import unittest
from solution import merge_intervals

class MergeTests(unittest.TestCase):
    def test_contract(self):
        self.assertEqual(merge_intervals([(5, 7), (1, 3), (3, 6)]), [(1, 7)])
        self.assertEqual(merge_intervals([(1, 10), (2, 3), (1, 10)]), [(1, 10)])
        self.assertEqual(merge_intervals([]), [])
        self.assertEqual(merge_intervals([[5, 7], (1, 3), [3, 6]]), [(1, 7)])
        pairs = [[1, 2], [3, 4]]
        result = merge_intervals(pairs)
        self.assertEqual(result, [(1, 2), (3, 4)])
        self.assertEqual(pairs, [[1, 2], [3, 4]])
        for value in [[(2, 2)], [(3, 1)], [(1, True)], [(1,)], None]:
            with self.assertRaises(ValueError):
                merge_intervals(value)

    def test_discrete_coverage_oracle(self):
        rng = random.Random(109)
        for _ in range(400):
            pairs = []
            for _ in range(rng.randrange(15)):
                start = rng.randrange(-8, 8)
                pairs.append((start, start + rng.randrange(1, 6)))
            result = merge_intervals(pairs)
            expected = {x for start, end in pairs for x in range(start, end)}
            actual = {x for start, end in result for x in range(start, end)}
            self.assertEqual(actual, expected)
            self.assertTrue(all(result[i][1] < result[i+1][0] for i in range(len(result)-1)))
            self.assertEqual(merge_intervals(result), result)

if __name__ == "__main__":
    unittest.main()