Intervals & Sweep Line

Calendars, train timetables, hotel bookings, server logs and video ad slots are all lists of intervals: things with a start and an end. Interval questions are among the most common in product-company interviews, and the same code runs inside every booking system that must say "this slot is taken".

This lesson gives you a small toolkit that covers most of them: a reliable overlap test, merging, intersecting two schedules with two pointers, the sweep line technique for counting overlaps, and assigning rooms with heaps. The Greedy Algorithms lesson already covered choosing the most non-overlapping events and counting railway platforms; here you go further.

Represent intervals the same way every time

Most bugs in interval code come from unclear ends. Pick one convention and state it out loud in an interview. This lesson uses half-open intervals [start, end): the start minute is included and the end minute is not. A meeting from 10:00 to 11:00 and one from 11:00 to 12:00 then do not overlap, which matches how people book rooms.

With half-open intervals, two intervals (a, b) and (c, d) overlap exactly when a < d and c < b. It is easier to remember the opposite: they do not overlap when one ends before the other starts.

def overlaps(x, y):
    (a, b), (c, d) = x, y
    return a < d and c < b

def overlap_length(x, y):
    return max(0, min(x[1], y[1]) - max(x[0], y[0]))

print(overlaps((600, 660), (660, 720)))   # 10:00-11:00 and 11:00-12:00
print(overlaps((600, 690), (660, 720)))   # 10:00-11:30 and 11:00-12:00
print(overlap_length((600, 690), (660, 720)), "minutes shared")

False
True
30 minutes shared

Times are stored as minutes after midnight, so 10:00 is 600. Storing times as numbers makes comparisons simple and avoids parsing bugs.

Merging overlapping intervals

Priya's team calendar in Pune lists busy blocks from several apps, many overlapping. To show a clean "busy" bar, merge them. Sort by start time; then each interval either overlaps the last merged block (extend it) or starts a new block.

def merge(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:       # touches or overlaps
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

busy = [(540, 600), (570, 630), (720, 780), (630, 660), (900, 960), (930, 945)]
print(merge(busy))

[[540, 660], [720, 780], [900, 960]]

Two details matter. max(...) handles an interval completely inside another, such as (930, 945) inside (900, 960). And <= joins blocks that only touch (600 to 630 and 630 to 660); for a busy bar that is what you want, even with half-open intervals. Sorting makes this O(n log n).

Intersecting two calendars with two pointers

Aarav and Ananya each have a sorted list of free slots with no overlaps inside a list. When can they both meet? Walk through both lists at once. The common part of the current pair is from the later start to the earlier end. Then move past whichever slot ends first, because it cannot overlap anything later in the other list.

def common_free(a_slots, b_slots, need=0):
    i = j = 0
    result = []
    while i < len(a_slots) and j < len(b_slots):
        start = max(a_slots[i][0], b_slots[j][0])
        end = min(a_slots[i][1], b_slots[j][1])
        if end - start >= max(need, 1):
            result.append((start, end))
        if a_slots[i][1] < b_slots[j][1]:
            i += 1
        else:
            j += 1
    return result

aarav = [(600, 690), (780, 840), (900, 1020)]
ananya = [(630, 660), (690, 800), (960, 1080)]
print(common_free(aarav, ananya))
print(common_free(aarav, ananya, need=45))

[(630, 660), (780, 800), (960, 1020)]
[(960, 1020)]

This is O(m + n), the same two-pointer idea as merging two sorted lists in Merge Sort. Scheduling tools use it to propose a meeting time for several people: intersect the first two calendars, then intersect the result with the next one.

The sweep line: turn intervals into events

How many people were on a video call at its busiest moment, and when? Imagine a vertical line sweeping from left to right across time. Split every interval into two events: +1 at its start and -1 at its end. Sort the events by time and add them up as you go; the running total is the number of active intervals.

Ties need a rule. With half-open intervals, someone leaving at minute 30 and someone joining at minute 30 never overlap, so process the -1 before the +1. Sorting (time, delta) tuples does this automatically, because -1 sorts before +1.

def peak_overlap(intervals):
    events = []
    for start, end in intervals:
        events.append((start, +1))
        events.append((end, -1))
    events.sort()                         # ends before starts at the same time
    active = best = 0
    best_time = None
    for time, delta in events:
        active += delta
        if active > best:
            best, best_time = active, time
    return best, best_time

# join and leave minute of each participant in a class
call = [(0, 30), (5, 50), (10, 20), (30, 45), (30, 60), (40, 55)]
print(peak_overlap(call))

(4, 40)

At minute 40, four people were active: (5, 50), (30, 45), (30, 60) and (40, 55). Sweeping is O(n log n) for the sort, and it works for any time range, even one with times in seconds over a whole year. A difference array gives the same counts in O(n + T), but only when the time range T is small enough to fit in a list.

Assigning rooms with two heaps

Counting rooms is not enough for a real booking system: each meeting must get a specific room, and staff prefer the lowest-numbered free room. Process meetings by start time with two heaps (see Heaps & Priority Queues):

• busy: (end_time, room) for rooms in use, so the room that frees up first is on top.
• free: room numbers that are available, so the smallest is on top.

import heapq

def assign_rooms(meetings):
    busy, free = [], []
    next_room = 1
    plan = {}
    for name, start, end in sorted(meetings, key=lambda m: m[1]):
        while busy and busy[0][0] <= start:          # release finished rooms
            _, room = heapq.heappop(busy)
            heapq.heappush(free, room)
        if free:
            room = heapq.heappop(free)
        else:
            room, next_room = next_room, next_room + 1
        plan[name] = room
        heapq.heappush(busy, (end, room))
    return plan, next_room - 1

meetings = [("Standup", 540, 555), ("Design review", 545, 600), ("Interview", 550, 610),
            ("Lunch talk", 560, 620), ("Client call", 600, 660), ("Retro", 615, 660)]
plan, rooms = assign_rooms(meetings)
for name, room in plan.items():
    print(f"{name:14} room {room}")
print("rooms used:", rooms)

Standup        room 1
Design review  room 2
Interview      room 3
Lunch talk     room 1
Client call    room 2
Retro          room 3
rooms used: 3

Each meeting causes at most a few heap operations, so the whole plan is O(n log n). With k rooms in a fixed building, you would start with all k rooms in free and, when it is empty, delay or reject the meeting.

Common mistakes

• Mixing closed and half-open intervals in the same program. Decide once and write it in a comment.
• Sorting by end when you need start, or the opposite. Merging and room assignment sort by start; choosing the most events sorts by end.
• Forgetting nested intervals when merging: always take max(end).
• Processing starts before ends at the same time in a sweep, which overcounts by one at every handover.
• Comparing time strings such as "9:30" < "10:00" (this is False, because "9" sorts after "1"). Convert to minutes first.

Key points

• Use half-open [start, end) intervals; they overlap exactly when a < d and c < b.
• Merge by sorting on start and extending the last block with max(end).
• Intersect two sorted lists with two pointers, moving past the interval that ends first.
• A sweep line turns intervals into +1/-1 events; sort them (ends first on ties) and keep a running count.
• Assign concrete rooms with a heap of busy rooms by end time and a heap of free room numbers.
• Most interval solutions are O(n log n), dominated by the sort.

def total_covered(sessions):
    total = 0
    cur_start = cur_end = None
    for start, end in sorted(sessions):
        if start >= end:
            continue                                  # empty session
        if cur_end is None or start > cur_end:        # a gap: close the block
            if cur_end is not None:
                total += cur_end - cur_start
            cur_start, cur_end = start, end
        else:
            cur_end = max(cur_end, end)
    if cur_end is not None:
        total += cur_end - cur_start
    return total

print(total_covered([(10, 30), (25, 40), (50, 55), (52, 70), (80, 80)]))

50