Meeting room scheduler

Design a scheduler that books meeting rooms. A request names the number of people and a time slot, and the scheduler finds a free room that is big enough. Two meetings never share a room at the same time.

Design a meeting room scheduler for an office. Rooms have a capacity. A person asks for a meeting for some number of attendees at a start time and an end time. The scheduler finds a free room that fits and books it. It refuses when there is a conflict, and a meeting can be cancelled.

Questions to ask first

  • How do we handle time? Assume whole minutes from midnight, 0 to 1440, for one day. There is no real clock and no calendar dates.
  • Is the end minute part of the meeting? Assume no. A meeting from 540 to 600 uses the minutes 540 to 599, so another meeting can start at 600 in the same room.
  • Does the person choose the room? Assume no. The scheduler chooses a room that fits and is free.
  • Which room should it choose when several fit? Assume the smallest room that fits, and the name that comes first when sizes are equal. This keeps large rooms free for large meetings.
  • What if no room is free? Assume the request is refused with a clear answer. Suggesting another time is an extension.
  • Do we track which people attend? Assume no. We only count them. A person's own calendar is an extension.
  • Can two people book at the same time? Yes. Assume one process with many threads, and two meetings must never get the same room and minute.

Requirements

  • Keep a set of rooms, each with a name and a capacity.
  • Book a meeting for a number of attendees and a time slot in a free room that fits.
  • Choose among the rooms that fit with one clear rule, so the same request gives the same room.
  • Refuse a request when no room that fits is free for the whole slot.
  • Refuse an invalid request, such as an end that is not after the start.
  • Cancel a meeting so its room is free for that slot again.
  • List the rooms that could host a request, in the order the scheduler would choose them.

Out of scope

  • People's own calendars, invitations and reminders.
  • Recurring meetings and time zones.
  • Room equipment, floors and distance.
  • Saving data to a database (in-memory storage is enough).

Entities

  • MeetingScheduler: addRoom(room), schedule(title, attendees, slot), cancel(id), candidates(attendees, slot)
  • Room: name, capacity, calendar
  • RoomCalendar: the slots booked in one room; isFree(slot), tryBook(slot), release(slot)
  • TimeSlot: start, end; overlaps(other)
  • Meeting: id, title, room, slot; cancel()
  • RoomSelectionStrategy: order(), the rule for which fitting room is tried first
  • SmallestFitStrategy: smallest capacity first, then name

Classes in the model design

  • MeetingScheduler (class)
  • Room (class)
  • RoomCalendar (class)
  • TimeSlot (class)
  • Meeting (class)
  • RoomSelectionStrategy (interface)
  • SmallestFitStrategy (class)

The main use case, step by step

  1. Asha needs a room for 3 people from minute 540 to minute 600. The app calls `scheduler.schedule("Standup", 3, new TimeSlot(540, 600))`.
  2. The scheduler keeps the rooms that have capacity 3 or more and are free for the slot. With rooms Everest (10), Nilgiri (6), Kailash (4) and Annapurna (4), all four qualify.
  3. It sorts them with the `RoomSelectionStrategy`. `SmallestFitStrategy` puts capacity 4 first, and between Annapurna and Kailash the name that comes first wins, so the order is Annapurna, Kailash, Nilgiri, Everest.
  4. The scheduler calls `tryBook(slot)` on the first room's calendar. The calendar checks its booked slots with `overlaps`, adds the slot and returns true, all in one synchronized step. If another thread took that room a moment earlier, it returns false and the scheduler tries the next room.
  5. On success the scheduler creates `Meeting` M1 with the room and slot, stores it and returns it. If every candidate fails, it returns nothing and the caller reports that no room is free.
  6. Cancelling M1 calls `meeting.cancel()`, which tells the room's calendar to `release(slot)`. The next request for minutes 540 to 600 can use Annapurna again.

Patterns used

  • Strategy: RoomSelectionStrategy (SmallestFitStrategy) is held by MeetingScheduler.. Offices want different choice rules: smallest room, first room, or the room used least. With an interface, a new rule is a new class and the scheduler is untouched (the open/closed principle).
  • Value object: TimeSlot holds a start and an end minute and owns the overlap rule.. Passing two loose numbers around leads to mixed-up order and repeated checks. A small class keeps the rule in one place, where it is easy to test on its edges.
  • Calendar per room (atomic check and add): RoomCalendar.tryBook is synchronized on that room.. A free check followed by a separate add lets two threads book the same minute. One synchronized step prevents it, and requests for different rooms never wait for each other.

Key code

TimeSlot, RoomCalendar and the room choice rule

/** The minutes from start up to, but not including, end. */
record TimeSlot(int start, int end) {

    static boolean valid(int start, int end) { return start >= 0 && end <= 1440 && start < end; }

    /** Two slots clash when each one starts before the other ends. */
    boolean overlaps(TimeSlot other) {
        return start < other.end && other.start < end;
    }
}

class RoomCalendar {
    private final List<TimeSlot> booked = new ArrayList<>();

    synchronized boolean isFree(TimeSlot slot) {
        for (TimeSlot s : booked) if (s.overlaps(slot)) return false;
        return true;
    }

    /** Check and add as one step. Two threads cannot both get true for the same minute. */
    synchronized boolean tryBook(TimeSlot slot) {
        if (!isFree(slot)) return false;
        booked.add(slot);
        return true;
    }

    synchronized void release(TimeSlot slot) { booked.remove(slot); }
}

interface RoomSelectionStrategy {
    Comparator<Room> order();
}

/** Smallest room that fits first, so large rooms stay free for large meetings. */
class SmallestFitStrategy implements RoomSelectionStrategy {
    @Override
    public Comparator<Room> order() {
        return Comparator.<Room>comparingInt(r -> r.capacity).thenComparing(r -> r.name);
    }
}

MeetingScheduler: find a room and book it

class MeetingScheduler {
    private final List<Room> rooms = new CopyOnWriteArrayList<>();
    private final Map<String, Meeting> meetings = new ConcurrentHashMap<>();
    private final RoomSelectionStrategy strategy;
    private final AtomicInteger nextId = new AtomicInteger();

    MeetingScheduler(RoomSelectionStrategy strategy) { this.strategy = strategy; }

    /** Rooms that are big enough and free for the whole slot, in the order we would try them. */
    List<Room> candidates(int attendees, TimeSlot slot) {
        List<Room> fit = new ArrayList<>();
        for (Room r : rooms) {
            if (r.capacity >= attendees && r.calendar.isFree(slot)) fit.add(r);
        }
        fit.sort(strategy.order());
        return fit;
    }

    /** Returns null when no room is free. If a thread wins a room first, we move to the next one. */
    Meeting schedule(String title, int attendees, TimeSlot slot) {
        for (Room room : candidates(attendees, slot)) {
            if (room.calendar.tryBook(slot)) {
                Meeting m = new Meeting("M" + nextId.incrementAndGet(), title, room, slot);
                meetings.put(m.id, m);
                return m;
            }
        }
        return null;
    }
}

Deep dives

The interval overlap rule

Weak: Compare start times for equality, or ask only whether the new start is inside an existing meeting. Take an existing meeting from 570 to 630 and a new request from 540 to 660. The new start is not inside the old meeting, so this test says the room is free. But the new request covers the old meeting.

Good: Check three cases: the new start is inside the old meeting, the new end is inside it, or the new request contains it. It is correct, but it is long, and boundaries such as a meeting that ends exactly when the next one starts are easy to get wrong.

Great: Treat each slot as the minutes from the start up to, but not including, the end. Slots a to b and c to d overlap exactly when a < d and c < b. They do not overlap only if one ends on or before the other starts. Negate that and you get the rule. Check the edge: 540 to 600 and 600 to 660 give 540 < 660 and 600 < 600. The second part is false, so they do not clash, and back-to-back meetings are allowed. Put the rule in TimeSlot.overlaps and write tests for touching, equal, nested and partly overlapping slots.

Trade-off: The rule depends on one convention: the start minute is included and the end minute is not. If another part of the code treats the end minute as used, you would need <= there, and back-to-back meetings would be wrongly refused. Pick one convention, write it as a comment, and use it everywhere.

Choosing the room

Weak: Take the first room in the list that fits. A 2-person meeting can then use the 10-person room, and a later 9-person meeting has nowhere to go. The answer also depends on the order in which rooms were added, so the same request can give different rooms in different runs.

Good: Choose the smallest room that fits, and when two rooms have the same capacity, the name that comes first. The rule is fixed, so the same input always gives the same room, and large rooms stay free for large meetings. Write this rule down so the interviewer and the tests agree on it.

Great: Put the rule behind a RoomSelectionStrategy that returns the order in which fitting rooms are tried. The scheduler keeps the rooms that fit and are free, sorts them with the strategy and books the first. freeRooms uses the same list, so what it shows is what schedule would do. A new rule, such as the room used least, is a new class.

Trade-off: The smallest-fit rule is a greedy choice and does not give the best packing of all meetings for the day. Finding the best packing is a harder problem, and an interview does not ask for it. Say that the greedy rule is simple, predictable and good enough, and name what you would change if the office complained.

Conflicts and two people booking at once

Weak: Check that the room is free, then add the meeting, as two separate steps. Two people can both see Annapurna free from 540 to 600 and both add a meeting. One room now holds two meetings at the same time. This is a race condition: the result depends on which thread runs first.

Good: Make schedule synchronized. Check and add happen as one step for the whole scheduler, so a double booking is impossible. It is easy to explain. But every request waits for every other request, even for different rooms.

Great: Give each room its own calendar, and make the check and the add one synchronized step inside it: tryBook. The scheduler tries the candidate rooms in order and takes the first one that says yes. If another thread wins a room between the free check and tryBook, the scheduler moves on to the next candidate. Requests that end up in different rooms never wait for each other.

Trade-off: A lock inside one process protects nothing across several servers. Then the database must decide, with one conditional insert that fails when the slot clashes, and the caller tries the next room. For a conflict, a friendlier answer than a plain refusal is to return the free rooms or the next free slot.

Now add one more feature

  • Now suggest another time when no room is free. What changes? Add a method that walks the room calendars and returns the earliest slot of the same length that fits. `RoomCalendar` gets a `nextFree(length, from)` method. The strategy and the overlap rule stay as they are.
  • Now add room equipment, such as a projector. What changes? Give Room a set of features and let a request carry the features it needs. The scheduler filters the candidates on features before it sorts them. The strategy does not change.
  • Now book a meeting that repeats every day for 5 days. What changes? Add a `scheduleSeries` method that builds five slots and books them all or none. If one day fails, release the days already booked. It uses the same `tryBook` and `release`.
  • Now stop one person from being in two meetings at the same time. What changes? Give each person a `RoomCalendar`-like calendar and book the room and every attendee together. Always lock in the same order, for example by name, so two requests cannot wait on each other.
  • Now let someone move a meeting to a new slot. What changes? Add `reschedule`. It must book the new slot before it releases the old one, so the person never loses the room. If the new slot clashes, nothing changes.

What each level is expected to show

SDE-1: A clean diagram with the scheduler, Room, Meeting and a time slot class. Schedule and cancel work, the overlap test is correct on the boundary so back-to-back meetings are allowed, and the room choice follows one stated rule. Knows that two people can race.

SDE-2: Everything at SDE-1, plus the overlap rule derived and tested on its edges, and a calendar per room with an atomic check and add. The room choice sits behind a Strategy. Explains how the same guard moves to a database. Answers each extension by naming the classes that change.

Common mistakes

  • Testing overlap with only the new start or only the new end, which misses a new meeting that contains an old one.
  • Treating the end minute as used, so a meeting cannot start when the previous one ends.
  • Taking the first room that fits, so large rooms are used by small meetings and the result depends on the order rooms were added.
  • Checking that a room is free and adding the meeting as two separate steps, which lets two people book the same minute.
  • Passing start and end as two loose integers in many methods, so the overlap rule is repeated and sometimes wrong.
  • Not checking the request: an end before the start, zero attendees, or a time past the end of the day.
  • Keeping meetings only in a global list, so finding the conflicts of one room means scanning every meeting.

Lessons behind this answer