44 — LLD: Meeting Room Scheduler

Understanding the Problem

Design an in-memory scheduler that books meeting rooms. A room has a capacity. A booking covers an interval. Support one-off and weekly recurring meetings. Detect conflicts, find a free room of a given capacity for an interval, and list bookings for a day.

What is a Meeting Room Scheduler?

It is the intersection-of-intervals problem dressed up with rooms, capacity, and recurrence. The core invariant: for every room, no two confirmed intervals overlap.

---

Requirements

Clarifying Questions

You: Time zones?

Interviewer: Single time zone for v1.

Intervals are plain epoch milliseconds. DST is not a concern yet.

You: What does recurrence look like?

Interviewer: Weekly with an end-date or a count.

Keep the recurrence model small — WEEKLY with an until epoch.

You: Double-booking allowed with override?

Interviewer: No. Hard conflict rejection.

Strict conflict policy is default. A ConflictPolicy strategy could allow override later.

You: Concurrent booking attempts on the same room?

Interviewer: Yes, expect it during rushes like 10 a.m. slots.

Per-room lock to serialise only what must be serialised.

Final Requirements

1. Rooms have an ID and capacity.
2. Book one-off or weekly-recurring meetings.
3. Hard conflict rejection.
4. Find a free room of >= capacity for a given target interval.
5. List bookings for a given day.
6. Thread-safe booking per room.

Out of scope: multi-time-zone, participant invites, calendar integration, permissions.

---

Core Entities and Relationships

Entity	Responsibility
Interval	{start, end} epoch ms. Overlap helper.
Recurrence	{kind, until}. Currently only WEEKLY.
Booking	Room, interval, organiser, optional recurrence.
Room	{id, capacity}.
Scheduler	Add rooms, book, cancel, query.
BookingIndex	Per-room sorted interval set for O(log n) overlap check.
ConflictPolicy	Strategy for how conflicts are resolved (strict for v1).

Why a generator for recurrence? Because the number of concrete occurrences can be large, and you only need to iterate them against a target. yield gives you lazy iteration.

Why separate BookingIndex from Scheduler? So the scheduler does not care how intervals are stored. Array today, interval tree tomorrow.

Design is iterative — arrays are fine up to a few hundred bookings per room.

---

Class Design

Interval

Methods:

• overlaps(other) — start < other.end && other.start < end

Booking

State: id, roomId, organiser, interval, recurrence?

Methods:

• occurrences() — generator yielding concrete intervals

Scheduler

State:

• rooms: Map<id, {capacity, bookings, lock}>

Methods:

• addRoom(id, capacity)
• book(b) — with conflict check
• cancel(id)
• findFreeRoom(capacity, interval)
• listForDay(roomId, day)

Design principles at play:

• Single Responsibility — booking, index, scheduler.
• Strategy — ConflictPolicy.
• Iterator Pattern — recurrence as a generator.

---

Implementation

Core Logic: Conflict Detection

Bad approach: recompute occurrences of every booking on every check.

• O(bookings × occurrences) on every call. Catastrophic for long recurrences.

Good approach: index each booking by the first-occurrence and stop early as soon as occurrences pass the target end.

• Linear but with early exit.

Great approach: interval tree per room. hasConflict becomes O(log n + k). Recurrence expands lazily but the tree is built once and mutated on book/cancel.

Verification

Room R1 capacity 6.

1. Book {R1, 09:00–10:00, Alice} → no conflict. Accepted.
2. Book {R1, 09:30–10:30, Bob} → overlaps Alice. Rejected.
3. Book {R1, 10:00–11:00, Carol, WEEKLY until +4w} → occurrences at 10:00 this week, next week, etc. No conflict. Accepted.
4. findFreeRoom(4, {10:00–11:00 next Tuesday}) → Carol's recurrence occupies R1 next Tuesday. Returns null or another room.
5. Concurrent booking of the same slot → per-room lock ensures exactly one succeeds.

Thread Safety

• Per-room lock around book. Other rooms are independent — no cross-contention.
• findFreeRoom can attempt a read-only scan without a lock, then acquire the lock on the winner to confirm. Uses the classic "read under optimism, retry under lock" idiom.
• Production-scale: interval tree per room under a ReentrantReadWriteLock. Many concurrent reads, booking takes write lock briefly.

Complete Code Implementation

Java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;

record Interval(long start, long end) {
    boolean overlaps(Interval other) { return start < other.end() && other.start() < end; }
}

record Recurrence(String kind, long until) {}

class Booking {
    public final String id, roomId, organiser;
    public final Interval interval;
    public final Recurrence recurrence;

    public Booking(String id, String roomId, String organiser, Interval interval, Recurrence r) {
        this.id = id; this.roomId = roomId; this.organiser = organiser;
        this.interval = interval; this.recurrence = r;
    }

    public Iterable<Interval> occurrences() {
        List<Interval> out = new ArrayList<>();
        if (recurrence == null) { out.add(interval); return out; }
        long week = 7L * 24 * 60 * 60 * 1000;
        long s = interval.start(), e = interval.end();
        while (s <= recurrence.until()) {
            out.add(new Interval(s, e));
            s += week; e += week;
        }
        return out;
    }
}

class Scheduler {
    private static class Room {
        int capacity;
        List<Booking> bookings = new ArrayList<>();
        ReentrantLock lock = new ReentrantLock();
        Room(int c) { capacity = c; }
    }
    private final ConcurrentHashMap<String, Room> rooms = new ConcurrentHashMap<>();

    public void addRoom(String id, int capacity) { rooms.put(id, new Room(capacity)); }

    private boolean hasConflict(Room room, Interval target) {
        for (Booking b : room.bookings) {
            for (Interval occ : b.occurrences()) {
                if (occ.start() > target.end()) break;
                if (occ.overlaps(target)) return true;
            }
        }
        return false;
    }

    public Booking book(Booking b) {
        Room room = rooms.get(b.roomId);
        if (room == null) throw new IllegalArgumentException("NO_ROOM");
        room.lock.lock();
        try {
            for (Interval occ : b.occurrences()) {
                if (hasConflict(room, occ)) throw new IllegalStateException("CONFLICT");
            }
            room.bookings.add(b);
            return b;
        } finally { room.lock.unlock(); }
    }

    public String findFreeRoom(int capacity, Interval target) {
        for (Map.Entry<String, Room> e : rooms.entrySet()) {
            Room room = e.getValue();
            if (room.capacity < capacity) continue;
            room.lock.lock();
            try { if (!hasConflict(room, target)) return e.getKey(); }
            finally { room.lock.unlock(); }
        }
        return null;
    }
}

C++

#include <memory>
#include <mutex>
#include <string>
#include <unordered_map>
#include <vector>

struct Interval {
    long long start, end;
    bool overlaps(const Interval& o) const { return start < o.end && o.start < end; }
};

struct Recurrence { std::string kind; long long until; bool present = false; };

struct Booking {
    std::string id, roomId, organiser;
    Interval interval;
    Recurrence recurrence;

    std::vector<Interval> occurrences() const {
        if (!recurrence.present) return {interval};
        std::vector<Interval> out;
        long long week = 7LL * 24 * 60 * 60 * 1000;
        long long s = interval.start, e = interval.end;
        while (s <= recurrence.until) { out.push_back({s, e}); s += week; e += week; }
        return out;
    }
};

class Scheduler {
    struct Room {
        int capacity;
        std::vector<Booking> bookings;
        std::mutex mu;
    };
    std::unordered_map<std::string, std::shared_ptr<Room>> rooms;
    std::mutex roomsMu;

    bool hasConflict(Room& room, const Interval& target) {
        for (auto& b : room.bookings)
            for (auto& occ : b.occurrences()) {
                if (occ.start > target.end) break;
                if (occ.overlaps(target)) return true;
            }
        return false;
    }

public:
    void addRoom(const std::string& id, int cap) {
        std::lock_guard<std::mutex> g(roomsMu);
        rooms[id] = std::make_shared<Room>(Room{cap, {}, {}});
    }

    void book(const Booking& b) {
        std::shared_ptr<Room> room;
        { std::lock_guard<std::mutex> g(roomsMu); room = rooms[b.roomId]; }
        if (!room) throw std::runtime_error("NO_ROOM");
        std::lock_guard<std::mutex> g(room->mu);
        for (auto& occ : b.occurrences())
            if (hasConflict(*room, occ)) throw std::runtime_error("CONFLICT");
        room->bookings.push_back(b);
    }

    std::string findFreeRoom(int capacity, const Interval& target) {
        std::lock_guard<std::mutex> g(roomsMu);
        for (auto& [id, room] : rooms) {
            if (room->capacity < capacity) continue;
            std::lock_guard<std::mutex> rg(room->mu);
            if (!hasConflict(*room, target)) return id;
        }
        return "";
    }
};

TypeScript

interface Interval { start: number; end: number; }

function overlaps(a: Interval, b: Interval): boolean {
  return a.start < b.end && b.start < a.end;
}

interface Recurrence { kind: "WEEKLY"; until: number; }

class Booking {
  constructor(
    public readonly id: string,
    public readonly roomId: string,
    public readonly organiser: string,
    public readonly interval: Interval,
    public readonly recurrence?: Recurrence,
  ) {}

  *occurrences(): Generator<Interval> {
    if (!this.recurrence) { yield this.interval; return; }
    const week = 7 * 24 * 60 * 60 * 1000;
    let start = this.interval.start;
    let end = this.interval.end;
    while (start <= this.recurrence.until) {
      yield { start, end };
      start += week; end += week;
    }
  }
}

class Scheduler {
  private rooms = new Map<string, { capacity: number; bookings: Booking[] }>();

  addRoom(id: string, capacity: number) { this.rooms.set(id, { capacity, bookings: [] }); }

  private hasConflict(roomId: string, target: Interval): boolean {
    const room = this.rooms.get(roomId);
    if (!room) return false;
    for (const b of room.bookings) {
      for (const occ of b.occurrences()) {
        if (occ.start > target.end) break;
        if (overlaps(occ, target)) return true;
      }
    }
    return false;
  }

  book(b: Booking): Booking {
    if (this.hasConflict(b.roomId, b.interval)) throw new Error("CONFLICT");
    if (b.recurrence) {
      for (const occ of b.occurrences()) {
        if (this.hasConflict(b.roomId, occ)) throw new Error("CONFLICT");
      }
    }
    this.rooms.get(b.roomId)!.bookings.push(b);
    return b;
  }

  findFreeRoom(capacity: number, target: Interval): string | null {
    for (const [id, room] of this.rooms) {
      if (room.capacity < capacity) continue;
      if (!this.hasConflict(id, target)) return id;
    }
    return null;
  }

  listForDay(roomId: string, dayStart: number): Interval[] {
    const dayEnd = dayStart + 24 * 60 * 60 * 1000;
    const target = { start: dayStart, end: dayEnd };
    const room = this.rooms.get(roomId);
    if (!room) return [];
    const out: Interval[] = [];
    for (const b of room.bookings) {
      for (const occ of b.occurrences()) {
        if (occ.start >= dayEnd) break;
        if (overlaps(occ, target)) out.push(occ);
      }
    }
    return out.sort((a, b) => a.start - b.start);
  }
}

---

Extensibility

1. "Reschedule"

Treat as cancel + book under a single lock so observers see one event. The interface stays the same — reschedule(bookingId, newInterval) is a convenience that wraps both.

2. "Notifications on conflict"

Observer pattern on Booking.onConfirmed. Email, Slack, calendar subscribers register at the Scheduler level. Failed sends are isolated per subscriber.

3. "DST and time zones"

Store interval in UTC epoch ms, but carry the organiser's IANA zone on the booking. Display-time conversion happens outside the core. Recurrence uses local wall time semantics (8 a.m. Monday in their zone) — compute each occurrence's UTC instant via the zone database.

---

What is Expected at Each Level

Level	Expectations
Mid	Arrays + linear overlap scan, no recurrence.
Senior / SMTS	Interval handling, recurrence via generator, clean conflict check, per-room locks, find-free-room.
Staff	Sharding rooms across nodes, calendar integration contract, DST and time-zone reasoning, interval-tree performance story.