Cruxly

Cruxly › Low-level design › LLD Exercises

Meeting Room Scheduler

booking a room is an interval-overlap problem wearing a calendar's clothes

Open the interactive lesson

Prompt: design a meeting room booking system for an office. Users book a room for a time range; the system must reject a booking that overlaps an existing one for the same room, support recurring meetings (e.g. "every Monday at 10am"), and let a user list all bookings for a room or a day.

45 minutes. The interesting part isn't the calendar UI — it's that "no overlap" is a precise interval-comparison rule, and recurring meetings turn a simple interval check into an infinite-series problem if you don't bound it up front.

Applying the five moves: nouns are Room, Booking (a single interval), and RecurrenceRule — keeping recurrence as a rule that generates bounded bookings, rather than one Booking object trying to represent infinitely many occurrences, is the move-2 decision the exercise turns on. The invariant is "no two bookings for the same room have overlapping intervals" — one inequality, stated before any calendar logic, and it's what makes the overlap check a single reusable primitive instead of a per-feature special case. The interface seam is RecurrenceRule (weekly, daily, custom — implementations of one interface), because "recurring meetings" is the prompt explicitly naming a variation point. Concurrency: two users booking the same room at the same time is check-then-act exactly like the rate limiter — the overlap check and the insert have to be atomic together, or two non-overlapping-looking bookings can both succeed and then collide.

Scope, and the overlap test that is the actual primitive

In scope: single-room booking with overlap rejection, listing bookings per room/day, recurring meetings with a bounded horizon, cancelling a single occurrence of a recurring series. Out of scope (say it): multi-room "find any available room" search (a related but distinct exercise — resource allocation across a pool, not interval checking for one resource), timezone handling beyond a single timezone, room capacity/equipment matching.

Two intervals [s1, e1) and [s2, e2) overlap if and only if s1 < e2 AND s2 < e1. This single inequality is the entire overlap test — there is no need for separate cases for "new meeting starts during an existing one," "new meeting contains an existing one," or "existing meeting contains the new one." Writing four separate if branches for these cases (a common first instinct) is a sign the general rule wasn't found; the interviewer is listening for whether you derive the one-line test or enumerate cases by hand.

Half-open intervals [start, end) avoid an off-by-one at the boundary. A meeting ending at 10:00 and one starting at 10:00 should not conflict — treating end as exclusive makes back-to-back bookings legal without a special case, while a closed interval [start, end] would require an explicit "unless they touch exactly" carve-out.

The classes, and storing bookings for a fast overlap check

public record TimeRange(Instant start, Instant end) {
    boolean overlaps(TimeRange other) {
        return start.isBefore(other.end) && other.start.isBefore(end);
    }
}

public class Room {
    private final String roomId;
    // Sorted by start time: overlap checks and "list bookings for a day"
    // both want ordered access, not an unordered set scanned every time.
    private final TreeMap<Instant, Booking> bookingsByStart = new TreeMap<>();

    /** O(log n) candidate lookup instead of scanning every booking:
     *  only bookings starting near the new range can possibly overlap it. */
    boolean hasConflict(TimeRange range) {
        var candidate = bookingsByStart.floorEntry(range.end());
        while (candidate != null && candidate.getValue().range().start().isBefore(range.end())) {
            if (candidate.getValue().range().overlaps(range)) return true;
            candidate = bookingsByStart.lowerEntry(candidate.getKey());
        }
        return false;
    }
}

A TreeMap keyed by start time turns "does this overlap anything" from an O(n) scan into a bounded walk backward from the new range's end — only bookings that start before the new booking ends can possibly overlap it, and once a candidate's start is at or before the new range's start with no overlap, nothing earlier can overlap either (they'd have to end even earlier). This is the same "structure the data so the check is bounded, not the same shape as brute force" instinct as the rate limiter's sliding-window log elsewhere in this track, applied to interval overlap instead of a request count.

Booking is a two-step operation — check, then insert — and it has the exact check-then-act shape covered throughout this track. Two users racing to book the same free slot must not both succeed; hasConflict followed by bookingsByStart.put needs the same atomicity discipline as the movie-booking exercise's seat hold, just with an interval-overlap check standing in for a status check.

Recurring meetings: materialize a bounded horizon, don't model infinity

A recurrence rule ("every Monday at 10am") describes infinitely many meetings, and the exercise is refusing to represent them all. The correct move is materializing concrete occurrences only up to a bounded horizon (say, 90 days out), re-materializing as the horizon rolls forward, rather than trying to answer "does this conflict" against an infinite abstract rule directly.

public class RecurringSeries {
    private final TimeRange firstOccurrence;
    private final Duration period;              // e.g. 7 days for weekly
    private final Set<LocalDate> cancelledDates; // exceptions: this occurrence was cancelled

    List<TimeRange> materialize(Instant horizon) {
        List<TimeRange> occurrences = new ArrayList<>();
        TimeRange current = firstOccurrence;
        while (current.start().isBefore(horizon)) {
            if (!cancelledDates.contains(dateOf(current.start()))) {
                occurrences.add(current);
            }
            current = shift(current, period);
        }
        return occurrences;
    }
}

Cancelling a single occurrence of a series must not touch the series' own definition — cancelledDates is a set of exceptions layered on top of the generating rule, not a mutation of firstOccurrence or period. This is the same distinction as an override in an inheritance hierarchy: the base rule stays intact, and a specific date's exception is checked before trusting the rule's output, the same "generate, then filter by exception" shape used for any recurring-event system.

Follow-ups they will ask

"Find any available room for a 2pm-3pm meeting, out of 500 rooms." This is a genuinely different problem from single-room overlap checking — it's a resource-allocation search, not an interval comparison. Maintaining a per-room TreeMap as above and querying "which rooms have no conflict in this range" across all 500 is a linear scan over rooms unless rooms are pre-indexed by their busy intervals in a shared structure (an interval tree keyed by room), which is the right escalation to name if the interviewer pushes on scale.

"Two users try to book the last available slot at the exact same time." This is the check-then-act race named in the second section, made concrete — the fix is the same atomic-claim discipline as the rate limiter and the movie-booking seat hold: the check-and-insert into bookingsByStart must happen inside one lock (or one atomic compare-and-swap against the room's booking state), not as two separate operations a second thread can interleave between.

"What if the recurrence rule itself changes — 'move this whole series from Mondays to Tuesdays going forward'?" This splits the series at the point of change: occurrences before the change keep the old rule (already materialized, already possibly attended), and a new RecurringSeries starts from the change point with the new rule — mutating the single rule in place would silently rewrite history for already-past occurrences that users have already seen and planned around.

How to say it in the interview

"Booking a room reduces to interval scheduling: reject a new [start, end) if it overlaps any existing interval for that room, and the overlap test itself is one inequality, not a special case per direction. Recurring meetings are the actual exercise, because a rule like 'every Monday' generates infinitely many intervals unless I materialize only a bounded horizon and treat exceptions as a real, separate concept."

Checklist

Practice this interactively
Share this lessonWhatsAppLinkedInX

Related lessons