Meeting room scheduler

import java.time.*;
import java.time.format.DateTimeFormatter;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.Consumer;

enum Feature { PROJECTOR, VIDEO_CONF, WHITEBOARD }

/**
 * A half-open interval [start, end). 10:00-11:00 and 11:00-12:00 do NOT conflict.
 * Say this convention out loud in the interview - it IS part of the answer.
 */
record TimeSlot(Instant start, Instant end) {
    TimeSlot {
        Objects.requireNonNull(start);
        Objects.requireNonNull(end);
        if (!start.isBefore(end)) throw new IllegalArgumentException("end must be after start");
    }

    /** THE predicate. One line, no case analysis, strict "<" on both sides. */
    boolean overlaps(TimeSlot other) {
        return start.isBefore(other.end) && other.start.isBefore(end);
    }

    /** Local wall time plus a zone -> a UTC instant. Storage is always UTC. */
    static TimeSlot on(LocalDate day, int fromHour, int toHour, ZoneId zone) {
        return new TimeSlot(day.atTime(fromHour, 0).atZone(zone).toInstant(),
                            day.atTime(toHour, 0).atZone(zone).toInstant());
    }

    String show(ZoneId zone) {
        var day = DateTimeFormatter.ofPattern("MM-dd");
        var time = DateTimeFormatter.ofPattern("HH:mm");
        return day.format(start.atZone(zone)) + " " + time.format(start.atZone(zone))
             + "-" + time.format(end.atZone(zone));
    }
}

record Booking(String id, String roomId, String organiser, TimeSlot slot, List<String> attendees) {}

/** The swappable seam: one contract, three cost profiles. */
interface AvailabilityIndex {
    Optional<Booking> firstConflict(TimeSlot slot);
    void add(Booking booking);
    void remove(String bookingId);
    int size();
}

/** O(n) per query. Boring, honest, and the right answer for one building. */
class LinearIndex implements AvailabilityIndex {
    private final List<Booking> bookings = new ArrayList<>();
    public Optional<Booking> firstConflict(TimeSlot slot) {
        for (Booking b : bookings) if (b.slot().overlaps(slot)) return Optional.of(b);
        return Optional.empty();
    }
    public void add(Booking b) { bookings.add(b); }
    public void remove(String id) { bookings.removeIf(b -> b.id().equals(id)); }
    public int size() { return bookings.size(); }
}

/**
 * O(log n). The entries are sorted by start AND non-overlapping, so only the booking
 * immediately before and the one immediately after the insertion point can conflict.
 */
class SortedIndex implements AvailabilityIndex {
    private final NavigableMap<Instant, Booking> byStart = new TreeMap<>();

    public Optional<Booking> firstConflict(TimeSlot slot) {
        var before = byStart.floorEntry(slot.start());
        if (before != null && before.getValue().slot().overlaps(slot)) return Optional.of(before.getValue());
        var after = byStart.ceilingEntry(slot.start());
        if (after != null && after.getValue().slot().overlaps(slot)) return Optional.of(after.getValue());
        return Optional.empty();   // nothing else can reach across those two
    }
    public void add(Booking b) { byStart.put(b.slot().start(), b); }
    public void remove(String id) { byStart.values().removeIf(b -> b.id().equals(id)); }
    public int size() { return byStart.size(); }
}

class Room {
    final String id, label;
    final int seats;
    final Set<Feature> features;                       // data, NOT subclasses
    final ReentrantLock lock = new ReentrantLock();    // per ROOM - R1 never waits on R3
    private final AvailabilityIndex index;

    Room(String id, String label, int seats, Set<Feature> features, AvailabilityIndex index) {
        this.id = id; this.label = label; this.seats = seats;
        this.features = Set.copyOf(features); this.index = index;
    }

    boolean suits(int minSeats, Set<Feature> needed) {
        return seats >= minSeats && features.containsAll(needed);
    }
    Optional<Booking> firstConflict(TimeSlot slot) { return index.firstConflict(slot); }
    void add(Booking b) { index.add(b); }
    void remove(String id) { index.remove(id); }
}

class ConflictException extends RuntimeException {
    final Booking clash;
    ConflictException(Booking clash) {
        super("clashes with " + clash.id());           // names WHICH booking
        this.clash = clash;
    }
}

/** Generates occurrences; never stores one row per day. */
record RecurrenceRule(Frequency freq, LocalDate until, ZoneId zone) {
    enum Frequency { DAILY, WEEKLY }
    static final int MAX_OCCURRENCES = 260;            // cap the horizon, always

    List<LocalDate> occurrences(LocalDate from) {
        List<LocalDate> out = new ArrayList<>();
        int step = freq == Frequency.DAILY ? 1 : 7;
        for (LocalDate d = from; !d.isAfter(until) && out.size() < MAX_OCCURRENCES; d = d.plusDays(step))
            out.add(d);
        return out;
    }
}

class Scheduler {
    private final Map<String, Room> rooms = new LinkedHashMap<>();
    private final List<Consumer<String>> listeners = new CopyOnWriteArrayList<>();
    private int lastId = 400;

    void addRoom(Room r) { rooms.put(r.id, r); }
    void onEvent(Consumer<String> listener) { listeners.add(listener); }
    private void publish(String msg) { listeners.forEach(l -> l.accept(msg)); }
    private synchronized String nextId() { return "B" + (++lastId); }

    Booking book(String roomId, TimeSlot slot, String organiser, List<String> attendees) {
        Room room = rooms.get(roomId);
        if (room == null) throw new IllegalArgumentException("no such room: " + roomId);
        room.lock.lock();                              // check AND write, one indivisible step
        try {
            var clash = room.firstConflict(slot);
            if (clash.isPresent()) throw new ConflictException(clash.get());
            Booking b = new Booking(nextId(), roomId, organiser, slot, List.copyOf(attendees));
            room.add(b);
            publish("booked " + b.id() + " in " + roomId);
            return b;
        } finally {
            room.lock.unlock();
        }
    }

    /** Capacity and features filter FIRST, time second. */
    Optional<Booking> findRoom(TimeSlot slot, int minSeats, Set<Feature> needed, String organiser) {
        for (Room r : rooms.values()) {
            if (!r.suits(minSeats, needed)) continue;
            try { return Optional.of(book(r.id, slot, organiser, List.of())); }
            catch (ConflictException busy) { /* try the next room */ }
        }
        return Optional.empty();
    }

    /** A series conflicts if ANY occurrence conflicts. Check them all, then write them all. */
    List<Booking> bookRecurring(String roomId, LocalDate from, int fromHour, int toHour,
                                RecurrenceRule rule, String organiser) {
        Room room = rooms.get(roomId);
        room.lock.lock();
        try {
            List<TimeSlot> slots = new ArrayList<>();
            for (LocalDate day : rule.occurrences(from)) {
                // 9am LOCAL on every occurrence - the UTC instant moves when the clocks do
                TimeSlot slot = TimeSlot.on(day, fromHour, toHour, rule.zone());
                var clash = room.firstConflict(slot);
                if (clash.isPresent())
                    throw new IllegalStateException("series refused: " + day + " clashes with " + clash.get().id());
                slots.add(slot);
            }
            List<Booking> made = new ArrayList<>();
            for (TimeSlot slot : slots) {
                Booking b = new Booking(nextId(), roomId, organiser, slot, List.of());
                room.add(b);
                made.add(b);
            }
            publish("booked a " + made.size() + "-occurrence series in " + roomId);
            return made;
        } finally {
            room.lock.unlock();
        }
    }

    void cancel(String roomId, String bookingId) {
        Room room = rooms.get(roomId);
        room.lock.lock();
        try { room.remove(bookingId); publish("cancelled " + bookingId); }
        finally { room.lock.unlock(); }
    }

    /** "How many rooms do these meetings need?" Sort by start, min-heap of end times. */
    static int roomsNeeded(List<TimeSlot> meetings) {
        List<TimeSlot> sorted = new ArrayList<>(meetings);
        sorted.sort(Comparator.comparing(TimeSlot::start));
        PriorityQueue<Instant> endsInUse = new PriorityQueue<>();
        int peak = 0;
        for (TimeSlot m : sorted) {
            // half-open: a room ending exactly when this starts is reusable
            if (!endsInUse.isEmpty() && !endsInUse.peek().isAfter(m.start())) endsInUse.poll();
            endsInUse.add(m.end());
            peak = Math.max(peak, endsInUse.size());
        }
        return peak;                                   // the PEAK, not the final size
    }
}

public class Main {
    static final ZoneId ZONE = ZoneId.of("Europe/London");

    public static void main(String[] args) throws Exception {
        Scheduler scheduler = new Scheduler();
        scheduler.addRoom(new Room("R1", "Huddle", 4, Set.of(), new SortedIndex()));
        scheduler.addRoom(new Room("R2", "Sync", 8, Set.of(Feature.PROJECTOR), new SortedIndex()));
        scheduler.addRoom(new Room("R3", "Boardroom", 12,
                Set.of(Feature.PROJECTOR, Feature.VIDEO_CONF), new SortedIndex()));
        scheduler.onEvent(msg -> System.out.println("   [notify] " + msg));

        LocalDate mon = LocalDate.of(2026, 3, 23);

        System.out.println("-- back to back is allowed --");
        scheduler.book("R2", TimeSlot.on(mon, 10, 11, ZONE), "ana", List.of("bo"));
        scheduler.book("R2", TimeSlot.on(mon, 11, 12, ZONE), "bo", List.of("ana"));
        System.out.println("   10-11 and 11-12 both booked: [start, end) is half-open");

        System.out.println("-- an overlapping request is refused --");
        try { scheduler.book("R2", TimeSlot.on(mon, 11, 13, ZONE), "cy", List.of()); }
        catch (ConflictException e) { System.out.println("   refused: " + e.getMessage()); }

        System.out.println("-- find any room seating 8 with a projector --");
        var found = scheduler.findRoom(TimeSlot.on(mon, 11, 12, ZONE), 8, Set.of(Feature.PROJECTOR), "dee");
        System.out.println("   -> " + found.map(b -> b.roomId() + " " + b.slot().show(ZONE)).orElse("nothing free"));

        System.out.println("-- a recurring series is all-or-nothing --");
        scheduler.book("R1", TimeSlot.on(mon.plusDays(2), 9, 10, ZONE), "eli", List.of());
        try {
            scheduler.bookRecurring("R1", mon, 9, 10,
                    new RecurrenceRule(RecurrenceRule.Frequency.DAILY, mon.plusDays(4), ZONE), "ana");
        } catch (IllegalStateException e) { System.out.println("   " + e.getMessage()); }

        System.out.println("-- how many rooms do these five meetings need? --");
        List<TimeSlot> five = List.of(
                TimeSlot.on(mon, 9, 12, ZONE), TimeSlot.on(mon, 9, 11, ZONE),
                TimeSlot.on(mon, 10, 13, ZONE), TimeSlot.on(mon, 11, 12, ZONE),
                TimeSlot.on(mon, 13, 15, ZONE));
        System.out.println("   rooms needed: " + Scheduler.roomsNeeded(five));

        System.out.println("-- two people book the same slot at the same instant --");
        var gate = new CountDownLatch(1);
        var pool = Executors.newFixedThreadPool(2);
        List<Future<String>> race = new ArrayList<>();
        for (String who : List.of("fay", "gus")) {
            race.add(pool.submit(() -> {
                gate.await();
                try {
                    var b = scheduler.book("R3", TimeSlot.on(mon, 15, 16, ZONE), who, List.of());
                    return who + " got " + b.id();
                } catch (ConflictException e) {
                    return who + " refused: " + e.getMessage();
                }
            }));
        }
        gate.countDown();
        for (var f : race) System.out.println("   " + f.get());
        pool.shutdown();
        System.out.println("exactly one winner, because check and write share the room's lock");
    }
}

/* expected output (the two racers may swap places):

-- back to back is allowed --
   [notify] booked B401 in R2
   [notify] booked B402 in R2
   10-11 and 11-12 both booked: [start, end) is half-open
-- an overlapping request is refused --
   refused: clashes with B402
-- find any room seating 8 with a projector --
   [notify] booked B403 in R3
   -> R3 03-23 11:00-12:00
-- a recurring series is all-or-nothing --
   [notify] booked B404 in R1
   series refused: 2026-03-25 clashes with B404
-- how many rooms do these five meetings need? --
   rooms needed: 3
-- two people book the same slot at the same instant --
   [notify] booked B405 in R3
   fay got B405
   gus refused: clashes with B405
exactly one winner, because check and write share the room's lock
*/