Intervals: Sort, Then Sweep

What an interval is. A pair [start, end]: a meeting, a booking, a request that held a lock, a range of IDs. Two intervals overlap when each one starts before the other ends. Whether [1, 4] and [4, 5] overlap depends on the story (are the endpoints included?). Decide first, and write the answer in the comparison.

Merge overlapping intervals. Sort by start. Keep the last merged block. If the next interval starts at or before that block's end, stretch the block to the larger end; otherwise it starts a new block. Sorting is what makes the check local: after it, an interval can only overlap the block just before it.

def merge(intervals):
    out = []
    for start, end in sorted(intervals):
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)   # extend, do not replace
        else:
            out.append([start, end])
    return out

merge([[1, 3], [2, 6], [8, 10], [15, 18]])   # [[1, 6], [8, 10], [15, 18]]
merge([[1, 4], [4, 5]])                      # [[1, 5]] (touching counts)

The max matters. A long interval can swallow shorter ones that come after it, as in [1, 10] then [2, 3]. Taking the larger end keeps the block at 10.

Sweep line: how many are open at once? Turn each interval into two events: +1 at its start, -1 at its end. Sort the events and keep a running total; the highest total is the most overlap, which is the number of meeting rooms you need. When an end and a start share a time, process the end first if the interval is half-open (a meeting ending at 2 frees the room for one starting at 2).

def most_overlap(intervals):
    events = []
    for s, e in intervals:
        events.append((s, 1))
        events.append((e, -1))
    events.sort()                # at equal times -1 sorts before +1
    cur = best = 0
    for _, d in events:
        cur += d
        best = max(best, cur)
    return best

most_overlap([[0, 30], [5, 10], [15, 20]])   # 2
most_overlap([[1, 2], [2, 3]])               # 1

Pick the most that fit. To keep as many non-overlapping intervals as possible, sort by end time and take every interval that starts at or after the last chosen end. Finishing earliest leaves the most room for the rest. [[1, 3], [2, 4], [3, 5], [0, 6], [5, 7]] gives 3 (1-3, 3-5, 5-7). Sorting by start would be wrong here: a single long meeting at the front would block everything.

Insert one interval into a sorted list in three passes: copy everything that ends before the new one starts, merge everything that overlaps it, copy the rest. No sort is needed because the list is already sorted.

Where it runs in production. Calendar and room booking, merging time ranges in logs and metrics, finding the busiest minute of traffic, allocating ranges of IDs or IPs, and the 'is this slot free?' check of every scheduler.