Design a Meeting Room / Calendar Booking System

Core classes

class Room { String id; int capacity; List<Booking> bookings; }
class Booking { String id; Room room; Instant start; Instant end; RecurrenceRule recurrence; }
interface RecurrenceRule { List<Interval> expand(Instant windowStart, Instant windowEnd); }
class AvailabilityChecker { boolean isAvailable(Room room, Instant start, Instant end); }

Separating Booking (a single reservation) from RecurrenceRule (an interface describing HOW a booking repeats) keeps the core booking model simple while letting recurrence be an independent, swappable concern — a daily standup and a one-off interview both produce Booking objects; only their recurrence behavior differs.

Efficient overlap detection

boolean isAvailable(Room room, Instant start, Instant end) {
    // naive: O(n) scan of every existing booking
    for (Booking b : room.getBookings()) {
        if (start.isBefore(b.end) && b.start.isBefore(end)) return false; // classic interval overlap check
    }
    return true;
}

Two intervals [s1,e1) and [s2,e2) overlap exactly when s1 < e2 AND s2 < e1 — this single condition (not four separate cases) is the standard, correct overlap test, directly reusable from Merge Intervals' interval reasoning. A naive per-room linear scan is fine at small scale; at real scale, each room's bookings are better kept in a SORTED structure (a tree ordered by start time), letting a new booking request binary-search to the relevant neighborhood rather than scanning every existing booking — the same efficiency principle behind Meeting Rooms II's sorted-sweep approach, applied here to a single room's own booking list.

Recurring meetings without materializing every instance

class WeeklyRecurrence implements RecurrenceRule {
    DayOfWeek day; LocalTime time; Duration duration; Instant recurrenceEnd;
    public List<Interval> expand(Instant windowStart, Instant windowEnd) {
        // computes only the occurrences WITHIN the requested window, on demand
    }
}

A naive implementation might insert a separate Booking row for every future occurrence of a recurring meeting the moment it's created ("every Monday for the next 2 years" → hundreds of rows immediately) — this wastes storage for occurrences that may never happen (the series could be cancelled next month) and makes editing the WHOLE series afterward require updating every materialized row. The better approach stores the recurrence RULE once, and expand() computes concrete occurrences ON DEMAND, only for whatever window is actually being queried (e.g. "show me next week's bookings") — this is the same lazy-computation principle behind not pre-computing data you might never need.

Overlap checks with a sorted interval map

For a single room, keep bookings in a TreeMap keyed by start time. A new booking [start, end) conflicts only if its nearest neighbours overlap it: the booking that starts at or before start, and the first booking that starts after it. You never need to scan the whole list:

final class RoomCalendar {
    private final TreeMap<Instant, Booking> byStart = new TreeMap<>();

    /** Intervals are half-open [start, end): a 10:00–11:00 meeting and an 11:00–12:00 meeting don't clash. */
    synchronized boolean tryBook(Booking b) {
        if (!b.start().isBefore(b.end())) throw new IllegalArgumentException("start must be before end");

        Map.Entry<Instant, Booking> before = byStart.floorEntry(b.start());
        if (before != null && before.getValue().end().isAfter(b.start())) return false;    // previous one runs into us

        Map.Entry<Instant, Booking> after = byStart.ceilingEntry(b.start());
        if (after != null && after.getKey().isBefore(b.end())) return false;                // next one starts before we end

        byStart.put(b.start(), b);
        return true;
    }

    synchronized List<Booking> between(Instant from, Instant to) {
        Instant key = Optional.ofNullable(byStart.floorKey(from)).orElse(from);        // include one already running
        return byStart.subMap(key, true, to, false).values().stream()
                .filter(x -> x.end().isAfter(from)).toList();
    }
}

• O(log n) per check and insert, instead of O(n).
• Two intervals overlap exactly when a.start < b.end && b.start < a.end. With half-open intervals, back-to-back meetings are allowed, which is what users expect.
• The check-then-insert happens under one lock, per room, so two people can't grab the same slot at the same moment. In a database, the equivalent is a transaction with a conditional insert, or PostgreSQL's exclusion constraint: EXCLUDE USING gist (room_id WITH =, tstzrange(start_at, end_at) WITH &&), which makes overlaps impossible at the storage level.

Recurring series with exceptions

Storing a rule (WEEKLY on TUE, 10:00–10:30, until 30 June) instead of every occurrence is compact, but users edit and cancel single occurrences. The standard model, used by iCalendar (RFC 5545) and every major calendar, is a series plus exceptions:

record Series(String id, String roomId, RecurrenceRule rule, LocalTime start, Duration length, ZoneId zone) {}

record Override(String seriesId, LocalDate originalDate,
                boolean cancelled, Instant newStart, Instant newEnd) {}     // moved or cancelled occurrence

final class OccurrenceExpander {
    List<Interval> expand(Series s, List<Override> overrides, LocalDate from, LocalDate to) {
        Map<LocalDate, Override> byDate = overrides.stream()
                .collect(Collectors.toMap(Override::originalDate, o -> o));
        List<Interval> result = new ArrayList<>();
        for (LocalDate d : s.rule().datesBetween(from, to)) {
            Override o = byDate.get(d);
            if (o != null && o.cancelled()) continue;                                   // skip cancelled date
            if (o != null) { result.add(new Interval(o.newStart(), o.newEnd())); continue; }   // moved occurrence
            ZonedDateTime start = d.atTime(s.start()).atZone(s.zone());                 // local time in the series' zone
            result.add(new Interval(start.toInstant(), start.plus(s.length()).toInstant()));
        }
        return result;
    }
}

• "Edit this occurrence" writes an Override for that date.
• "Edit this and following" ends the current series the day before, and starts a new series.
• The time zone belongs to the series. A weekly 10:00 meeting in Mumbai stays at 10:00 local time. Storing only UTC instants would shift it for participants in regions with daylight-saving changes.
• To check a new booking against recurring series, expand only the relevant window (the dates of the new booking), not the whole series.

Finding a free slot for several people

"Find 30 minutes when these five people and a room are all free" is an interval problem:

1. Collect every busy interval for the participants and candidate rooms in the search window.
2. Sort them by start, and merge overlapping ones (the Merge Intervals technique).
3. Walk the gaps between merged intervals, and return the first gap at least 30 minutes long that falls within working hours.

That's O(k log k) for k busy intervals. The same merge-and-scan logic powers "suggested times" features.

Follow-up questions this topic invites — and their answers

Q: How do you handle editing a single occurrence of a recurring series ("just this Tuesday's meeting is moved"), given occurrences aren't materialized? A: A common pattern adds an explicit EXCEPTION list to the recurrence rule (specific dates that deviate from the base rule, either cancelled or moved) — expand() then applies the base rule and overlays exceptions, rather than forcing a full materialize-then-edit model just to support the single-occurrence-edit case.

Q: Does the overlap check need to account for time zones? A: Yes, critically — comparing Instant values (an absolute point in time, not a wall-clock time) sidesteps time zone ambiguity entirely for the overlap CHECK itself; time zones only matter for DISPLAYING the booking to a user in their local time, a presentation-layer concern kept separate from the core availability logic.

Q: How would you scale availability checking across thousands of rooms simultaneously (e.g. 'find any available room for 2pm')? A: This shifts from a per-room overlap check to a genuine search problem — indexing rooms by capacity/location and maintaining each room's near-term booked intervals in a fast-queryable structure lets a 'find available' query filter candidates efficiently, rather than checking every room's full booking list linearly for every search.

Q: How does this design relate to Meeting Rooms II, the DSA problem? A: Meeting Rooms II answers a narrower analytical question — given a fixed list of intervals, what's the PEAK concurrent count — using the same sort-and-sweep technique that a real booking system's capacity-planning or reporting feature would reuse; the LLD system here is the broader, stateful, ongoing service that a query like Meeting Rooms II might run AGAINST, not a replacement for it.

Q: Why use a TreeMap for one room's bookings? A: It keeps bookings sorted by start time, so a conflict check only has to examine the immediate predecessor and successor of the new booking. That's O(log n) instead of scanning every booking.

Q: How do you store an edit to one occurrence of a recurring meeting? A: Keep the series rule unchanged, and add an exception record for that occurrence's original date, marking it cancelled or giving its new time. Expansion applies exceptions as it generates occurrences. "This and following" edits split the series into two.

Q: How can the database itself prevent double bookings? A: Use a constraint that forbids overlapping ranges for the same room. PostgreSQL supports this with an exclusion constraint on (room_id, tstzrange(start, end)) using the && overlap operator. Concurrent inserts that would overlap then fail, instead of both succeeding.