DSA Inserting an Interval

The problem

Insert Interval places one new span into a calendar that is already sorted and merged. The calendar holds spans in start order with no overlaps. The new span is the only disorder in the input.

The answer is the same calendar with the new span placed and merged. Every span the new span overlaps or touches is absorbed into one wider span. Spans clear of it stay untouched.

cases = [
    ([(1, 2), (3, 5), (6, 7), (8, 10), (12, 16)], (4, 8), [(1, 2), (3, 10), (12, 16)]),
    ([(1, 3), (6, 9)], (2, 5), [(1, 5), (6, 9)]),
    ([(1, 5)], (6, 8), [(1, 5), (6, 8)]),
    ([], (5, 7), [(5, 7)]),
]
for spans, new, expected in cases:
    print("calendar", spans, "insert", new, "->", expected)

Read the first row slowly. The new span (4, 8) absorbs three spans and grows into (3, 10). The spans (1, 2) and (12, 16) never touch it and survive unchanged.

Intuition: placing the span is not the same as merging it

The first idea drops the new span into its sorted position by start time. The calendar stays sorted after that drop. Sorted feels finished, and that feeling is the trap.

Position fixes order only. The placed span can still overlap its new neighbours on both sides. A sorted calendar with overlaps is not a merged calendar.

calendar = [(1, 2), (3, 5), (6, 7), (8, 10), (12, 16)]
placed = sorted(calendar + [(4, 8)])
print("placed:", placed)
overlapping = 0
for i in range(1, len(placed)):
    if placed[i][0] <= placed[i - 1][1]:
        overlapping += 1
print("adjacent overlapping pairs:", overlapping)

Two adjacent pairs overlap after placement. The new span reaches into the span before it and the spans after it. The real work is the absorbing, not the placing.

Brute force: rebuild the whole calendar from scratch

The brute force ignores that the calendar was already merged. It appends the new span and then merges any overlapping pair, rescanning after every merge, until no pair overlaps.

That rebuild is correct for any input at all. Its cost is the pair scanning. The counters below record the pair tests and merges on the main case.

def insert_brute(spans, new):
    work = [list(s) for s in spans] + [list(new)]
    comparisons = 0
    merges = 0
    changed = True
    while changed:
        changed = False
        for i in range(len(work)):
            for j in range(i + 1, len(work)):
                comparisons += 1
                a, b = work[i], work[j]
                if a[0] <= b[1] and b[0] <= a[1]:
                    work[i] = [min(a[0], b[0]), max(a[1], b[1])]
                    del work[j]
                    merges += 1
                    changed = True
                    break
            if changed:
                break
    return sorted(tuple(s) for s in work), comparisons, merges

calendar = [(1, 2), (3, 5), (6, 7), (8, 10), (12, 16)]
result, comparisons, merges = insert_brute(calendar, (4, 8))
print("after:", result)
print("pair tests:", comparisons, " merges:", merges)

Three merges were needed, and the scan restarted after each one. Almost every pair test examined spans that were already merged before the new span arrived. The sorted input offered a shortcut the brute force never takes.

The optimal solution: three groups in one pass

The merged span starts as a copy of the new span and grows as it absorbs neighbours, and each calendar span falls into exactly one of three groups against it. That one sentence is the whole method.

A span ending before the merged start belongs on the left. A span starting after the merged end belongs on the right. Every other span overlaps or touches, so it is absorbed and can stretch the merged span wider.

def insert(spans, new):
    left = []
    right = []
    merged = [new[0], new[1]]
    for s in spans:
        if s[1] < merged[0]:
            left.append(s)
        elif s[0] > merged[1]:
            right.append(s)
        else:
            merged[0] = min(merged[0], s[0])
            merged[1] = max(merged[1], s[1])
    return left + [tuple(merged)] + right

cases = [
    ([(1, 2), (3, 5), (6, 7), (8, 10), (12, 16)], (4, 8), [(1, 2), (3, 10), (12, 16)]),
    ([(1, 3), (6, 9)], (2, 5), [(1, 5), (6, 9)]),
    ([(1, 5)], (6, 8), [(1, 5), (6, 8)]),
    ([], (5, 7), [(5, 7)]),
]
for spans, new, expected in cases:
    result = insert(spans, new)
    print("insert", new, "into", spans, "->", result, "match:", result == expected)

All four cases pass in one pass each. The tests compare each span against the growing merged span, not the original new span. That order keeps the right group honest, because a span joins it only after clearing the grown end.

Walkthrough: inserting (4, 8) into the main calendar

The walk visits the five calendar spans in order. Each line names the group the span falls into. The merged span is printed whenever it grows.

calendar = [(1, 2), (3, 5), (6, 7), (8, 10), (12, 16)]
merged = [4, 8]
for s in calendar:
    if s[1] < merged[0]:
        print("span", s, "- left, untouched")
    elif s[0] > merged[1]:
        print("span", s, "- right, untouched")
    else:
        merged[0] = min(merged[0], s[0])
        merged[1] = max(merged[1], s[1])
        print("span", s, "- absorbed, merged is now", tuple(merged))
print("answer: [(1, 2), (3, 10), (12, 16)]")

Three spans are absorbed in a row. The first pulls the start down to 3. The third pushes the end up to 10. The answer is the left group, then the merged span, then the right group.

Complexity

The brute force rescans all pairs after every merge, so its time is O(n^2) or worse for n calendar spans. The three-group pass visits each span once and the calendar is already sorted, so its time is O(n).

The brute force copies every span into its work list, so its extra space is O(n). The three-group pass builds the answer list, which holds up to n plus 1 spans, so its space is O(n).

for n in [5, 10, 20]:
    pairs = (n + 1) * n // 2
    print("calendar spans", n, "- brute pair tests in one pass:", pairs, " three-group visits:", n)

At 20 spans one brute pass tests 210 pairs against 20 visits. The calendar arrived sorted and merged, and the one pass is the method that uses both facts.

Edge cases and pitfalls

A span ending exactly at the merged start is absorbed, not placed on the left. The left test is strict for that reason. The same strictness on the right lets a span starting exactly at the merged end be absorbed too.

The classic mistake is comparing every span against the original new span instead of the growing merged span. The merged span grows as it absorbs, and a test against the frozen original can leave a touching span outside a span it should join.

def insert(spans, new):
    left = []
    right = []
    merged = [new[0], new[1]]
    for s in spans:
        if s[1] < merged[0]:
            left.append(s)
        elif s[0] > merged[1]:
            right.append(s)
        else:
            merged[0] = min(merged[0], s[0])
            merged[1] = max(merged[1], s[1])
    return left + [tuple(merged)] + right

print("empty calendar:", insert([], (5, 7)))
print("new before all:", insert([(5, 6), (8, 9)], (1, 2)))
print("new after all:", insert([(1, 2), (3, 4)], (6, 8)))
print("touching merges:", insert([(1, 2), (8, 10)], (4, 8)))
print("new covers all:", insert([(1, 2), (4, 5), (7, 8)], (0, 9)))
print("new inside one span:", insert([(1, 10), (12, 15)], (3, 4)))

The touching row grows the new span to (4, 10). The inside row changes nothing, because the calendar span (1, 10) absorbs the new span whole. Both outcomes come from the same three tests, with no special cases.