The intervals pattern — merging, scheduling, and overlap problems

A surprising number of problems that look completely different on the surface — merging meetings, scheduling rooms, inserting a new event — collapse into the same shape once the intervals are sorted, which is the one insight that makes all of them tractable.

Intermediate

4 min read

The one setup step that makes every interval problem tractable: sort first

meetings = [(1, 3), (5, 8), (2, 6), (8, 10)]
meetings.sort(key=lambda interval: interval[0])  # sort by START time
# [(1, 3), (2, 6), (5, 8), (8, 10)]

Almost every interval problem starts with sorting by start time (occasionally by end time, depending on the specific question) — once sorted, two intervals can only possibly overlap with their immediate neighbors in the sorted order, never with something far away, which is what turns an otherwise all-pairs O(n²) comparison problem into a single O(n log n) sort followed by one O(n) linear pass.

Merging overlapping intervals: the canonical version of this pattern

def merge_intervals(intervals):
    intervals.sort(key=lambda i: i[0])
    merged = [intervals[0]]
 
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        if start <= last_end:                          # THIS interval overlaps the LAST merged one
            merged[-1] = (merged[-1][0], max(last_end, end))  # extend it, don't add a new entry
        else:
            merged.append((start, end))                 # no overlap — a genuinely NEW interval
 
    return merged
 
merge_intervals([(1, 3), (2, 6), (5, 8), (8, 10)])
# [(1, 10)] — all four overlap in a chain, so they collapse into one

The check start <= last_end is the entire mechanism: after sorting by start time, if the next interval's start is at or before the last merged interval's end, they overlap (or touch) and should merge into one — extending the last merged interval's end to whichever is larger. If not, the new interval genuinely starts a new, separate group. This single check, applied once per interval in the sorted list, correctly handles chains of overlaps (A overlaps B, which overlaps C, even if A and C don't directly overlap) without any extra logic.

Meeting rooms: does a schedule have ANY conflict at all

def can_attend_all(meetings):
    meetings.sort(key=lambda m: m[0])
    for i in range(1, len(meetings)):
        if meetings[i][0] < meetings[i - 1][1]:  # this meeting STARTS before the previous one ENDS
            return False  # a genuine conflict — one person can't attend both
    return True

After sorting by start time, a conflict can only ever occur between adjacent meetings in that sorted order — if meeting i starts before meeting i-1 ends, they overlap, and no valid single-person schedule can attend both. This is the exact same "sort, then compare only neighbors" insight as merging, applied to a yes/no question instead of a merge — the sort is what makes checking only adjacent pairs sufficient, rather than needing to compare every pair of meetings against each other.

Inserting a new interval into an already-sorted, non-overlapping list

def insert_interval(intervals, new_interval):
    result = []
    i = 0
    n = len(intervals)
 
    while i < n and intervals[i][1] < new_interval[0]:  # entirely BEFORE the new interval — keep as-is
        result.append(intervals[i])
        i += 1
 
    while i < n and intervals[i][0] <= new_interval[1]:  # OVERLAPS the new interval — merge it in
        new_interval = (min(new_interval[0], intervals[i][0]), max(new_interval[1], intervals[i][1]))
        i += 1
    result.append(new_interval)
 
    while i < n:  # entirely AFTER the new interval — keep as-is
        result.append(intervals[i])
        i += 1
 
    return result

Because the input is already sorted and non-overlapping (a real, common precondition for this variant of the problem), inserting one new interval only needs three passes: intervals entirely before the new one (copied unchanged), intervals that overlap it (merged into a single growing interval), and intervals entirely after (copied unchanged) — a single O(n) linear scan, since the sorted structure already guarantees which intervals could possibly overlap the new one, without needing to re-sort or re-check the whole list from scratch.

Recognizing the pattern: the actual signal to look for

The recurring signal across all of these: a problem described in terms of ranges, time windows, or "does X overlap with Y" — meetings, bookings, ranges of numbers, even byte ranges in a file — is very likely an interval problem, and the very first, near-automatic move should be sorting by start (or occasionally end) time before reaching for anything more complex. A surprising fraction of interval problems that look intimidating on first read turn out to be exactly this same sort-then-linear-scan shape underneath.