Concepts / State, data structures and algorithms inside objects / Intervals and scheduling

Intervals and scheduling

Meetings, bookings and conflicts as interval arithmetic.

Low-level design conceptState, data structures and algorithms inside objects2 Nov 2026

01The intuition

The problem it solves

A school has one hall. Teachers book it for lessons, each with a start and an end time. The first version stores bookings in a list and, for a new request, compares it against every existing booking with a condition that is easy to get wrong.

class Hall:
    def __init__(self) -> None:
        self.bookings: list[tuple[int, int]] = []     # (start, end) in minutes

    def book(self, start: int, end: int) -> bool:
        for s, e in self.bookings:
            if start >= s and start < e:          # misses the case where the new
                return False                      # booking swallows an old one
        self.bookings.append((start, end))
        return True

Try booking 9:00 to 12:00 when 10:00 to 11:00 already exists: the new start is before the old one, the check passes, and two classes now share the hall. Beyond the bug, every booking scans the whole list, and "when is the hall free for an hour" has no cheap answer at all.

Build it one piece at a time

Step one: get the overlap test right and give it a name. Two half-open intervals [a, b) and [c, d) overlap exactly when a is before d and c is before b. Half-open means a lesson ending at 11:00 and one starting at 11:00 do not clash.

from dataclasses import dataclass

@dataclass(frozen=True, order=True)
class Interval:
    start: int
    end: int

    def overlaps(self, other: "Interval") -> bool:
        return self.start < other.end and other.start < self.end

Step two: keep the bookings sorted by start. A new interval can only clash with its neighbours in sorted order: the last booking that starts before it and the first that starts after it. Binary search finds the position in log n, so a booking costs log n plus the list insert.

import bisect

class Hall:
    def __init__(self) -> None:
        self.bookings: list[Interval] = []        # sorted by start

    def book(self, start: int, end: int) -> bool:
        new = Interval(start, end)
        i = bisect.bisect_left(self.bookings, new)
        if i > 0 and self.bookings[i - 1].overlaps(new):
            return False
        if i < len(self.bookings) and self.bookings[i].overlaps(new):
            return False
        self.bookings.insert(i, new)
        return True

Step three: the questions that need the whole day, such as "how many halls are needed" or "where is the first free hour", use a sweep: turn every interval into a start event (+1) and an end event (−1), sort the events, and walk them with a running count. The maximum of the count is the number of halls; a gap in the count at zero is free time.

def halls_needed(bookings: list[Interval]) -> int:
    events: list[tuple[int, int]] = []
    for b in bookings:
        events.append((b.start, +1))
        events.append((b.end, -1))
    events.sort()                   # ends sort before starts at the same minute
    running = best = 0
    for _, delta in events:
        running += delta
        best = max(best, running)
    return best

Sweep over three bookings, 9:00 to 10:30, 10:00 to 11:00 and 10:30 to 12:00 (minutes from 9:00):

MinuteEventRunning count
0+1 (9:00 start)1
60+1 (10:00 start)2
90−1 (10:30 end)1
90+1 (10:30 start)2
120−11
180−10

Two halls are enough, and the end-before-start ordering at minute 90 is what lets a back-to-back booking reuse the hall.

Why it works

The sorted-list invariant is that bookings are pairwise non-overlapping and ordered by start; under that invariant, a candidate can only touch its two neighbours, which is why two checks are enough. The sweep's invariant is that the running count after processing minute t equals the number of bookings covering t, so its maximum is exactly the resource need.

Where it breaks: closed versus half-open intervals. If you store ends inclusively, back-to-back bookings clash and the sweep order flips. Pick half-open, write it in the class docstring, and test the touching case. The other trap is recurrence: a weekly booking is an infinite set of intervals, so expand it only within the queried range. Time zones and daylight saving are a third: store instants in UTC and convert at the edges.

booking: scan = n overlap tests; sorted list = log2 n search + 2 tests + O(n) insert; a balanced tree makes the insert log n too

The trade-off you must say out loud

A sorted list with bisect is simple and right for thousands of bookings; the O(n) insert only matters at millions, where an interval tree or a sorted container earns its complexity. Say that you start with the list and name the structure you would move to. The follow-up that usually comes next is capacity: a room that holds three meetings at once, which turns the neighbour check into a count over overlapping intervals and brings the sweep back.

Where it shows up in the 100 Google problems

02Used in these problems