Intervals

Sort-then-sweep for merging, inserting and meeting-room problems.

Interval problems — meetings, bookings, ranges — almost always start the same way: sort by start time, then sweep through once, comparing each interval to the last one you kept.

When to use it

Merging overlapping ranges
Inserting a new interval into a sorted list
Finding conflicts or the minimum number of rooms/resources
Finding free time or intersections between schedules

Overlap, precisely

Two intervals [a, b] and [c, d] overlap when a <= d and c <= b. Whether touching intervals ([1, 2] and [2, 3]) count as overlapping depends on the problem — ask.

Template: merge

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)   # extend
        else:
            merged.append([start, end])
    return merged

O(n log n) for the sort, then O(n).

Template: minimum rooms (sweep line)

Treat starts as +1 and ends as −1, and track the maximum running total:

def min_rooms(intervals):
    starts = sorted(s for s, _ in intervals)
    ends = sorted(e for _, e in intervals)
    rooms = best = j = 0
    for s in starts:
        while j < len(ends) and ends[j] <= s:   # a meeting ended; free its room
            rooms -= 1
            j += 1
        rooms += 1
        best = max(best, rooms)
    return best

The heap version (a min-heap of end times) gives the same result and also tells you *which* room each meeting uses.

Variations

Insert interval — add intervals ending before the new one, merge all that overlap, then add the rest. O(n), no sort needed if the input is sorted.
Non-overlapping intervals (min removals) — sort by end time and greedily keep the interval that ends earliest.
Interval intersections — two pointers over two sorted lists; advance the one that ends first.

[!TIP] Practice Merge Overlapping Intervals · Minimum Meeting Rooms