Design a Flight Booking System

from __future__ import annotations

import threading
from dataclasses import dataclass, field
from enum import Enum
from typing import Protocol

# Time is minutes since midnight, to keep the demo short. 10:05 is 605.


def hhmm(m: int) -> str:
    return f"{m // 60:02d}:{m % 60:02d}"


class Class(Enum):
    ECONOMY = "economy"
    BUSINESS = "business"


class State(Enum):
    """free -> held -> booked, or held -> free again."""
    FREE = "free"
    HELD = "held"
    BOOKED = "booked"


@dataclass
class Seat:
    no: str
    cls: Class
    state: State = State.FREE
    hold: str = ""


class Clock(Protocol):
    def now(self) -> int: ...


class Fare(Protocol):
    """Prices one seat. left = free seats of that class before this hold."""
    def price(self, cls: Class, left: int) -> int: ...


class ClassFare:
    def __init__(self, prices: dict[Class, int]):
        self.prices = prices

    def price(self, cls: Class, left: int) -> int:
        return self.prices[cls]


class Surge:
    """Wraps another Fare and adds percent when only `below` seats or fewer are left."""
    def __init__(self, base: Fare, below: int, percent: int):
        self.base, self.below, self.percent = base, below, percent

    def price(self, cls: Class, left: int) -> int:
        p = self.base.price(cls, left)
        return p + p * self.percent // 100 if left <= self.below else p


@dataclass
class Hold:
    id: str
    passenger: str
    seats: list[str]
    total: int
    expires: int


@dataclass
class Booking:
    pnr: str
    passenger: str
    seats: list[str]
    total: int


class Refused(Exception):
    pass


@dataclass
class Flight:
    code: str
    clock: Clock
    fare: Fare
    hold_for: int
    seats: dict[str, Seat] = field(default_factory=dict)  # insertion order = map order
    holds: dict[str, Hold] = field(default_factory=dict)
    expired: dict[str, int] = field(default_factory=dict)
    next_hold: int = 0
    next_pnr: int = 0
    lock: threading.Lock = field(default_factory=threading.Lock)

    def add_row(self, row: int, cls: Class, letters: str) -> None:
        with self.lock:
            for l in letters:
                self.seats[f"{row}{l}"] = Seat(f"{row}{l}", cls)

    def hold(self, passenger: str, *nos: str) -> Hold:
        """Keeps all the seats for one passenger, or none of them."""
        with self.lock:
            self._release_expired()
            if not nos:
                raise Refused("pick at least one seat")
            left: dict[Class, int] = {}
            for s in self.seats.values():
                if s.state is State.FREE:
                    left[s.cls] = left.get(s.cls, 0) + 1
            total, seen = 0, set()
            for no in nos:  # check every seat first, touch nothing
                s = self.seats.get(no)
                if s is None:
                    raise Refused(f"no seat {no}")
                if no in seen:
                    raise Refused(f"seat {no} picked twice")
                if s.state is not State.FREE:
                    raise Refused(f"seat {no} is {s.state.value}")
                seen.add(no)
                total += self.fare.price(s.cls, left.get(s.cls, 0))
            self.next_hold += 1
            h = Hold(f"H{self.next_hold}", passenger, list(nos), total, self.clock.now() + self.hold_for)
            for no in nos:
                self.seats[no].state, self.seats[no].hold = State.HELD, h.id
            self.holds[h.id] = h
            return h

    def pay(self, hold_id: str) -> Booking:
        with self.lock:
            self._release_expired()
            h = self.holds.pop(hold_id, None)
            if h is None:
                if hold_id in self.expired:
                    raise Refused(f"hold {hold_id} expired at {hhmm(self.expired[hold_id])}")
                raise Refused(f"no hold {hold_id}")
            for no in h.seats:
                self.seats[no].state, self.seats[no].hold = State.BOOKED, ""
            self.next_pnr += 1
            return Booking(f"PNR-{self.next_pnr}", h.passenger, list(h.seats), h.total)

    def release(self, hold_id: str) -> None:
        with self.lock:
            h = self.holds.pop(hold_id, None)
            if h is None:
                raise Refused(f"no hold {hold_id}")
            self._free(h)

    def all_seats(self) -> list[Seat]:
        with self.lock:
            self._release_expired()
            return [Seat(s.no, s.cls, s.state, s.hold) for s in self.seats.values()]

    def _release_expired(self) -> None:
        now = self.clock.now()
        for hid in [i for i, h in self.holds.items() if now >= h.expires]:
            h = self.holds.pop(hid)
            self._free(h)
            self.expired[hid] = h.expires

    def _free(self, h: Hold) -> None:
        for no in h.seats:
            self.seats[no].state, self.seats[no].hold = State.FREE, ""


class FakeClock:
    def __init__(self):
        self.t = 0

    def now(self) -> int:
        return self.t

    def set(self, s: str) -> None:
        h, m = s.split(":")
        self.t = int(h) * 60 + int(m)


def main() -> None:
    clock = FakeClock()
    fare = Surge(ClassFare({Class.ECONOMY: 5000, Class.BUSINESS: 12000}), below=1, percent=25)
    f = Flight("CF-141", clock, fare, hold_for=10)
    f.add_row(1, Class.BUSINESS, "AB")
    f.add_row(2, Class.ECONOMY, "ABC")
    f.add_row(3, Class.ECONOMY, "ABC")
    print("flight CF-141 Dhaka -> Cox's Bazar: 2 business, 6 economy, holds last 10 min")

    def hold(at: str, who: str, *seats: str) -> None:
        clock.set(at)
        label = f"{at} {who:<6} holds {' '.join(seats)}"
        try:
            h = f.hold(who, *seats)
            print(f"{label:<28} -> {h.id}, {h.total} tk, pay by {hhmm(h.expires)}")
        except Refused as e:
            print(f"{label:<28} -> refused: {e}")

    def pay(at: str, who: str, hid: str) -> None:
        clock.set(at)
        label = f"{at} {who:<6} pays {hid}"
        try:
            b = f.pay(hid)
            print(f"{label:<28} -> booked {b.pnr}: {' '.join(b.seats)}")
        except Refused as e:
            print(f"{label:<28} -> refused: {e}")

    hold("10:00", "Rahim", "2A", "2B")
    hold("10:01", "Nadia", "2B", "2C")
    hold("10:01", "Nadia", "2C", "3A")
    pay("10:03", "Rahim", "H1")
    hold("10:05", "Tania", "1A")
    pay("10:06", "Tania", "H3")
    pay("10:12", "Nadia", "H2")
    hold("10:12", "Sabbir", "2C", "3A", "3B")
    hold("10:13", "Karim", "3C")

    clock.set("10:14")
    f.release("H5")
    print(f"{'10:14 Karim  gives up H5':<28} -> 3C is free again")

    by: dict[State, list[str]] = {s: [] for s in State}
    for s in f.all_seats():
        by[s.state].append(s.no)
    print(f"10:14 booked: {' '.join(by[State.BOOKED])} | held: {' '.join(by[State.HELD])} | free: {' '.join(by[State.FREE])}")


if __name__ == "__main__":
    main()

// Time is minutes since midnight, to keep the demo short. 10:05 is 605.
const hhmm = (m: number) => `${String(Math.floor(m / 60)).padStart(2, "0")}:${String(m % 60).padStart(2, "0")}`;

type Class = "economy" | "business";
type State = "free" | "held" | "booked"; // free -> held -> booked, or held -> free again

interface Seat { no: string; cls: Class; state: State; hold: string }
interface Clock { now(): number }

/** Prices one seat. left = free seats of that class before this hold. */
interface Fare { price(cls: Class, left: number): number }

class ClassFare implements Fare {
  prices: Record<Class, number>;
  constructor(prices: Record<Class, number>) { this.prices = prices; }
  price(cls: Class): number { return this.prices[cls]; }
}

/** Wraps another Fare and adds percent when only `below` seats or fewer are left. */
class Surge implements Fare {
  base: Fare; below: number; percent: number;
  constructor(base: Fare, below: number, percent: number) {
    this.base = base; this.below = below; this.percent = percent;
  }
  price(cls: Class, left: number): number {
    const p = this.base.price(cls, left);
    return left <= this.below ? p + Math.floor((p * this.percent) / 100) : p;
  }
}

interface Hold { id: string; passenger: string; seats: string[]; total: number; expires: number }
interface Booking { pnr: string; passenger: string; seats: string[]; total: number }

class Refused extends Error {}

// One thread runs JavaScript, so a method can't be interrupted halfway: no lock needed.
class Flight {
  seats = new Map<string, Seat>(); // insertion order = map order
  holds = new Map<string, Hold>();
  expired = new Map<string, number>();
  nextHold = 0;
  nextPnr = 0;
  code: string; clock: Clock; fare: Fare; holdFor: number;
  constructor(code: string, clock: Clock, fare: Fare, holdFor: number) {
    this.code = code; this.clock = clock; this.fare = fare; this.holdFor = holdFor;
  }

  addRow(row: number, cls: Class, letters: string): void {
    for (const l of letters) this.seats.set(`${row}${l}`, { no: `${row}${l}`, cls, state: "free", hold: "" });
  }

  /** Keeps all the seats for one passenger, or none of them. */
  hold(passenger: string, ...nos: string[]): Hold {
    this.releaseExpired();
    if (nos.length === 0) throw new Refused("pick at least one seat");
    const left = new Map<Class, number>();
    for (const s of this.seats.values()) if (s.state === "free") left.set(s.cls, (left.get(s.cls) ?? 0) + 1);
    let total = 0;
    const seen = new Set<string>();
    for (const no of nos) { // check every seat first, touch nothing
      const s = this.seats.get(no);
      if (!s) throw new Refused(`no seat ${no}`);
      if (seen.has(no)) throw new Refused(`seat ${no} picked twice`);
      if (s.state !== "free") throw new Refused(`seat ${no} is ${s.state}`);
      seen.add(no);
      total += this.fare.price(s.cls, left.get(s.cls) ?? 0);
    }
    const h: Hold = { id: `H${++this.nextHold}`, passenger, seats: [...nos], total, expires: this.clock.now() + this.holdFor };
    for (const no of nos) Object.assign(this.seats.get(no)!, { state: "held", hold: h.id });
    this.holds.set(h.id, h);
    return h;
  }

  pay(holdId: string): Booking {
    this.releaseExpired();
    const h = this.holds.get(holdId);
    if (!h) {
      const at = this.expired.get(holdId);
      throw new Refused(at !== undefined ? `hold ${holdId} expired at ${hhmm(at)}` : `no hold ${holdId}`);
    }
    for (const no of h.seats) Object.assign(this.seats.get(no)!, { state: "booked", hold: "" });
    this.holds.delete(holdId);
    return { pnr: `PNR-${++this.nextPnr}`, passenger: h.passenger, seats: [...h.seats], total: h.total };
  }

  release(holdId: string): void {
    const h = this.holds.get(holdId);
    if (!h) throw new Refused(`no hold ${holdId}`);
    this.free(h);
    this.holds.delete(holdId);
  }

  allSeats(): Seat[] {
    this.releaseExpired();
    return [...this.seats.values()].map((s) => ({ ...s }));
  }

  private releaseExpired(): void {
    const now = this.clock.now();
    for (const [id, h] of this.holds) {
      if (now >= h.expires) {
        this.free(h);
        this.holds.delete(id);
        this.expired.set(id, h.expires);
      }
    }
  }

  private free(h: Hold): void {
    for (const no of h.seats) Object.assign(this.seats.get(no)!, { state: "free", hold: "" });
  }
}

class FakeClock implements Clock {
  t = 0;
  now(): number { return this.t; }
  set(s: string): void { const [h, m] = s.split(":").map(Number); this.t = h * 60 + m; }
}

function main(): void {
  const clock = new FakeClock();
  const fare = new Surge(new ClassFare({ economy: 5000, business: 12000 }), 1, 25);
  const f = new Flight("CF-141", clock, fare, 10);
  f.addRow(1, "business", "AB");
  f.addRow(2, "economy", "ABC");
  f.addRow(3, "economy", "ABC");
  console.log("flight CF-141 Dhaka -> Cox's Bazar: 2 business, 6 economy, holds last 10 min");

  const attempt = (label: string, fn: () => string) => {
    try {
      console.log(`${label.padEnd(28)} -> ${fn()}`);
    } catch (e) {
      if (!(e instanceof Refused)) throw e;
      console.log(`${label.padEnd(28)} -> refused: ${e.message}`);
    }
  };
  const hold = (at: string, who: string, ...seats: string[]) => {
    clock.set(at);
    attempt(`${at} ${who.padEnd(6)} holds ${seats.join(" ")}`, () => {
      const h = f.hold(who, ...seats);
      return `${h.id}, ${h.total} tk, pay by ${hhmm(h.expires)}`;
    });
  };
  const pay = (at: string, who: string, id: string) => {
    clock.set(at);
    attempt(`${at} ${who.padEnd(6)} pays ${id}`, () => {
      const b = f.pay(id);
      return `booked ${b.pnr}: ${b.seats.join(" ")}`;
    });
  };

  hold("10:00", "Rahim", "2A", "2B");
  hold("10:01", "Nadia", "2B", "2C");
  hold("10:01", "Nadia", "2C", "3A");
  pay("10:03", "Rahim", "H1");
  hold("10:05", "Tania", "1A");
  pay("10:06", "Tania", "H3");
  pay("10:12", "Nadia", "H2");
  hold("10:12", "Sabbir", "2C", "3A", "3B");
  hold("10:13", "Karim", "3C");

  clock.set("10:14");
  f.release("H5");
  console.log(`${"10:14 Karim  gives up H5".padEnd(28)} -> 3C is free again`);

  const by: Record<State, string[]> = { free: [], held: [], booked: [] };
  for (const s of f.allSeats()) by[s.state].push(s.no);
  console.log(`10:14 booked: ${by.booked.join(" ")} | held: ${by.held.join(" ")} | free: ${by.free.join(" ")}`);
}

main();

use std::collections::{HashMap, HashSet};
use std::sync::Mutex;

// Time is minutes since midnight, to keep the demo short. 10:05 is 605.
fn hhmm(m: u32) -> String {
    format!("{:02}:{:02}", m / 60, m % 60)
}

#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
enum Class {
    Economy,
    Business,
}

// free -> held -> booked, or held -> free again
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum State {
    Free,
    Held,
    Booked,
}

impl State {
    fn name(self) -> &'static str {
        match self {
            State::Free => "free",
            State::Held => "held",
            State::Booked => "booked",
        }
    }
}

#[derive(Clone, Debug)]
struct Seat {
    no: String,
    class: Class,
    state: State,
    hold: String,
}

trait Clock: Send + Sync {
    fn now(&self) -> u32;
}

/// Prices one seat. `left` = free seats of that class before this hold.
trait Fare: Send + Sync {
    fn price(&self, class: Class, left: u32) -> u32;
}

struct ClassFare(HashMap<Class, u32>);

impl Fare for ClassFare {
    fn price(&self, class: Class, _left: u32) -> u32 {
        self.0[&class]
    }
}

/// Wraps another Fare and adds `percent` when only `below` seats or fewer are left.
struct Surge {
    base: Box<dyn Fare>,
    below: u32,
    percent: u32,
}

impl Fare for Surge {
    fn price(&self, class: Class, left: u32) -> u32 {
        let p = self.base.price(class, left);
        if left <= self.below { p + p * self.percent / 100 } else { p }
    }
}

#[derive(Clone)]
struct Hold {
    id: String,
    passenger: String,
    seats: Vec<String>,
    total: u32,
    expires: u32,
}

struct Booking {
    pnr: String,
    #[allow(dead_code)]
    passenger: String,
    seats: Vec<String>,
    #[allow(dead_code)]
    total: u32,
}

// Everything that changes lives inside the Mutex, so you can't touch it without the lock.
#[derive(Default)]
struct Inner {
    order: Vec<String>,
    seats: HashMap<String, Seat>,
    holds: HashMap<String, Hold>,
    expired: HashMap<String, u32>,
    next_hold: u32,
    next_pnr: u32,
}

impl Inner {
    fn release_expired(&mut self, now: u32) {
        let gone: Vec<String> = self.holds.values().filter(|h| now >= h.expires).map(|h| h.id.clone()).collect();
        for id in gone {
            let h = self.holds.remove(&id).unwrap();
            self.free(&h);
            self.expired.insert(id, h.expires);
        }
    }

    fn free(&mut self, h: &Hold) {
        for no in &h.seats {
            let s = self.seats.get_mut(no).unwrap();
            s.state = State::Free;
            s.hold.clear();
        }
    }
}

struct Flight {
    #[allow(dead_code)]
    code: String,
    clock: Box<dyn Clock>,
    fare: Box<dyn Fare>,
    hold_for: u32,
    inner: Mutex<Inner>,
}

impl Flight {
    fn new(code: &str, clock: Box<dyn Clock>, fare: Box<dyn Fare>, hold_for: u32) -> Self {
        Flight { code: code.into(), clock, fare, hold_for, inner: Mutex::new(Inner::default()) }
    }

    fn add_row(&self, row: u32, class: Class, letters: &str) {
        let mut g = self.inner.lock().unwrap();
        for l in letters.chars() {
            let no = format!("{row}{l}");
            g.seats.insert(no.clone(), Seat { no: no.clone(), class, state: State::Free, hold: String::new() });
            g.order.push(no);
        }
    }

    /// Keeps all the seats for one passenger, or none of them.
    fn hold(&self, passenger: &str, nos: &[&str]) -> Result<Hold, String> {
        let now = self.clock.now();
        let mut g = self.inner.lock().unwrap();
        g.release_expired(now);
        if nos.is_empty() {
            return Err("pick at least one seat".into());
        }
        let mut left: HashMap<Class, u32> = HashMap::new();
        for s in g.seats.values().filter(|s| s.state == State::Free) {
            *left.entry(s.class).or_default() += 1;
        }
        let (mut total, mut seen) = (0, HashSet::new());
        for &no in nos {
            // check every seat first, touch nothing
            let s = g.seats.get(no).ok_or(format!("no seat {no}"))?;
            if !seen.insert(no) {
                return Err(format!("seat {no} picked twice"));
            }
            if s.state != State::Free {
                return Err(format!("seat {no} is {}", s.state.name()));
            }
            total += self.fare.price(s.class, left.get(&s.class).copied().unwrap_or(0));
        }
        g.next_hold += 1;
        let h = Hold {
            id: format!("H{}", g.next_hold),
            passenger: passenger.into(),
            seats: nos.iter().map(|s| s.to_string()).collect(),
            total,
            expires: now + self.hold_for,
        };
        for &no in nos {
            let s = g.seats.get_mut(no).unwrap();
            s.state = State::Held;
            s.hold = h.id.clone();
        }
        g.holds.insert(h.id.clone(), h.clone());
        Ok(h)
    }

    fn pay(&self, hold_id: &str) -> Result<Booking, String> {
        let now = self.clock.now();
        let mut g = self.inner.lock().unwrap();
        g.release_expired(now);
        let Some(h) = g.holds.remove(hold_id) else {
            return Err(match g.expired.get(hold_id) {
                Some(&at) => format!("hold {hold_id} expired at {}", hhmm(at)),
                None => format!("no hold {hold_id}"),
            });
        };
        for no in &h.seats {
            let s = g.seats.get_mut(no).unwrap();
            s.state = State::Booked;
            s.hold.clear();
        }
        g.next_pnr += 1;
        Ok(Booking { pnr: format!("PNR-{}", g.next_pnr), passenger: h.passenger, seats: h.seats, total: h.total })
    }

    fn release(&self, hold_id: &str) -> Result<(), String> {
        let mut g = self.inner.lock().unwrap();
        let h = g.holds.remove(hold_id).ok_or(format!("no hold {hold_id}"))?;
        g.free(&h);
        Ok(())
    }

    fn all_seats(&self) -> Vec<Seat> {
        let now = self.clock.now();
        let mut g = self.inner.lock().unwrap();
        g.release_expired(now);
        g.order.iter().map(|no| g.seats[no].clone()).collect()
    }
}

// The demo's clock: the story sets the time from outside, through a shared cell.
struct FakeClock(std::sync::Arc<Mutex<u32>>);

impl Clock for FakeClock {
    fn now(&self) -> u32 {
        *self.0.lock().unwrap()
    }
}

fn main() {
    let t = std::sync::Arc::new(Mutex::new(0u32));
    let set = |s: &str| {
        let (h, m) = s.split_once(':').unwrap();
        *t.lock().unwrap() = h.parse::<u32>().unwrap() * 60 + m.parse::<u32>().unwrap();
    };
    let base = ClassFare(HashMap::from([(Class::Economy, 5000), (Class::Business, 12000)]));
    let fare = Surge { base: Box::new(base), below: 1, percent: 25 };
    let f = Flight::new("CF-141", Box::new(FakeClock(t.clone())), Box::new(fare), 10);
    f.add_row(1, Class::Business, "AB");
    f.add_row(2, Class::Economy, "ABC");
    f.add_row(3, Class::Economy, "ABC");
    println!("flight CF-141 Dhaka -> Cox's Bazar: 2 business, 6 economy, holds last 10 min");

    let hold = |at: &str, who: &str, seats: &[&str]| {
        set(at);
        let label = format!("{at} {who:<6} holds {}", seats.join(" "));
        match f.hold(who, seats) {
            Ok(h) => println!("{label:<28} -> {}, {} tk, pay by {}", h.id, h.total, hhmm(h.expires)),
            Err(e) => println!("{label:<28} -> refused: {e}"),
        }
    };
    let pay = |at: &str, who: &str, id: &str| {
        set(at);
        let label = format!("{at} {who:<6} pays {id}");
        match f.pay(id) {
            Ok(b) => println!("{label:<28} -> booked {}: {}", b.pnr, b.seats.join(" ")),
            Err(e) => println!("{label:<28} -> refused: {e}"),
        }
    };

    hold("10:00", "Rahim", &["2A", "2B"]);
    hold("10:01", "Nadia", &["2B", "2C"]);
    hold("10:01", "Nadia", &["2C", "3A"]);
    pay("10:03", "Rahim", "H1");
    hold("10:05", "Tania", &["1A"]);
    pay("10:06", "Tania", "H3");
    pay("10:12", "Nadia", "H2");
    hold("10:12", "Sabbir", &["2C", "3A", "3B"]);
    hold("10:13", "Karim", &["3C"]);

    set("10:14");
    f.release("H5").unwrap();
    println!("{:<28} -> 3C is free again", "10:14 Karim  gives up H5");

    let seats = f.all_seats();
    let by = |st: State| seats.iter().filter(|s| s.state == st).map(|s| s.no.as_str()).collect::<Vec<_>>().join(" ");
    println!("10:14 booked: {} | held: {} | free: {}", by(State::Booked), by(State::Held), by(State::Free));
}

import java.util.*;

public class Main {
    // Time is minutes since midnight, to keep the demo short. 10:05 is 605.
    static String hhmm(int m) { return String.format("%02d:%02d", m / 60, m % 60); }

    enum SeatClass { ECONOMY, BUSINESS }

    // free -> held -> booked, or held -> free again
    enum State {
        FREE, HELD, BOOKED;
        String label() { return name().toLowerCase(); }
    }

    static final class Seat {
        final String no;
        final SeatClass cls;
        State state = State.FREE;
        String hold = "";
        Seat(String no, SeatClass cls) { this.no = no; this.cls = cls; }
    }

    interface Clock { int now(); }

    /** Prices one seat. left = free seats of that class before this hold. */
    interface Fare { int price(SeatClass cls, int left); }

    record ClassFare(Map<SeatClass, Integer> prices) implements Fare {
        public int price(SeatClass cls, int left) { return prices.get(cls); }
    }

    /** Wraps another Fare and adds percent when only `below` seats or fewer are left. */
    record Surge(Fare base, int below, int percent) implements Fare {
        public int price(SeatClass cls, int left) {
            int p = base.price(cls, left);
            return left <= below ? p + p * percent / 100 : p;
        }
    }

    record Hold(String id, String passenger, List<String> seats, int total, int expires) {}
    record Booking(String pnr, String passenger, List<String> seats, int total) {}

    static final class Refused extends Exception {
        private static final long serialVersionUID = 1L;
        Refused(String msg) { super(msg); }
    }

    static final class Flight {
        final String code;
        private final Clock clock;
        private final Fare fare;
        private final int holdFor;
        private final Map<String, Seat> seats = new LinkedHashMap<>(); // keeps map order
        private final Map<String, Hold> holds = new HashMap<>();
        private final Map<String, Integer> expired = new HashMap<>();
        private int nextHold, nextPnr;

        Flight(String code, Clock clock, Fare fare, int holdFor) {
            this.code = code; this.clock = clock; this.fare = fare; this.holdFor = holdFor;
        }

        synchronized void addRow(int row, SeatClass cls, String letters) {
            for (char l : letters.toCharArray()) seats.put(row + "" + l, new Seat(row + "" + l, cls));
        }

        /** Keeps all the seats for one passenger, or none of them. */
        synchronized Hold hold(String passenger, String... nos) throws Refused {
            releaseExpired();
            if (nos.length == 0) throw new Refused("pick at least one seat");
            Map<SeatClass, Integer> left = new EnumMap<>(SeatClass.class);
            for (Seat s : seats.values()) if (s.state == State.FREE) left.merge(s.cls, 1, Integer::sum);
            int total = 0;
            Set<String> seen = new HashSet<>();
            for (String no : nos) { // check every seat first, touch nothing
                Seat s = seats.get(no);
                if (s == null) throw new Refused("no seat " + no);
                if (!seen.add(no)) throw new Refused("seat " + no + " picked twice");
                if (s.state != State.FREE) throw new Refused("seat " + no + " is " + s.state.label());
                total += fare.price(s.cls, left.getOrDefault(s.cls, 0));
            }
            Hold h = new Hold("H" + ++nextHold, passenger, List.of(nos), total, clock.now() + holdFor);
            for (String no : nos) { seats.get(no).state = State.HELD; seats.get(no).hold = h.id(); }
            holds.put(h.id(), h);
            return h;
        }

        synchronized Booking pay(String holdId) throws Refused {
            releaseExpired();
            Hold h = holds.remove(holdId);
            if (h == null) {
                Integer at = expired.get(holdId);
                throw new Refused(at != null ? "hold " + holdId + " expired at " + hhmm(at) : "no hold " + holdId);
            }
            for (String no : h.seats()) { seats.get(no).state = State.BOOKED; seats.get(no).hold = ""; }
            return new Booking("PNR-" + ++nextPnr, h.passenger(), h.seats(), h.total());
        }

        synchronized void release(String holdId) throws Refused {
            Hold h = holds.remove(holdId);
            if (h == null) throw new Refused("no hold " + holdId);
            free(h);
        }

        synchronized Map<State, List<String>> seatsByState() {
            releaseExpired();
            Map<State, List<String>> by = new EnumMap<>(State.class);
            for (State st : State.values()) by.put(st, new ArrayList<>());
            for (Seat s : seats.values()) by.get(s.state).add(s.no);
            return by;
        }

        private void releaseExpired() {
            int now = clock.now();
            Iterator<Hold> it = holds.values().iterator();
            while (it.hasNext()) {
                Hold h = it.next();
                if (now >= h.expires()) { free(h); it.remove(); expired.put(h.id(), h.expires()); }
            }
        }

        private void free(Hold h) {
            for (String no : h.seats()) { seats.get(no).state = State.FREE; seats.get(no).hold = ""; }
        }
    }

    static int t = 0;

    static void set(String s) {
        String[] p = s.split(":");
        t = Integer.parseInt(p[0]) * 60 + Integer.parseInt(p[1]);
    }

    static Flight f;

    static void hold(String at, String who, String... seats) {
        set(at);
        String label = String.format("%s %-6s holds %s", at, who, String.join(" ", seats));
        try {
            Hold h = f.hold(who, seats);
            System.out.printf("%-28s -> %s, %d tk, pay by %s%n", label, h.id(), h.total(), hhmm(h.expires()));
        } catch (Refused e) {
            System.out.printf("%-28s -> refused: %s%n", label, e.getMessage());
        }
    }

    static void pay(String at, String who, String id) {
        set(at);
        String label = String.format("%s %-6s pays %s", at, who, id);
        try {
            Booking b = f.pay(id);
            System.out.printf("%-28s -> booked %s: %s%n", label, b.pnr(), String.join(" ", b.seats()));
        } catch (Refused e) {
            System.out.printf("%-28s -> refused: %s%n", label, e.getMessage());
        }
    }

    public static void main(String[] args) throws Refused {
        Fare fare = new Surge(new ClassFare(Map.of(SeatClass.ECONOMY, 5000, SeatClass.BUSINESS, 12000)), 1, 25);
        f = new Flight("CF-141", () -> t, fare, 10);
        f.addRow(1, SeatClass.BUSINESS, "AB");
        f.addRow(2, SeatClass.ECONOMY, "ABC");
        f.addRow(3, SeatClass.ECONOMY, "ABC");
        System.out.println("flight CF-141 Dhaka -> Cox's Bazar: 2 business, 6 economy, holds last 10 min");

        hold("10:00", "Rahim", "2A", "2B");
        hold("10:01", "Nadia", "2B", "2C");
        hold("10:01", "Nadia", "2C", "3A");
        pay("10:03", "Rahim", "H1");
        hold("10:05", "Tania", "1A");
        pay("10:06", "Tania", "H3");
        pay("10:12", "Nadia", "H2");
        hold("10:12", "Sabbir", "2C", "3A", "3B");
        hold("10:13", "Karim", "3C");

        set("10:14");
        f.release("H5");
        System.out.printf("%-28s -> 3C is free again%n", "10:14 Karim  gives up H5");

        var by = f.seatsByState();
        System.out.printf("10:14 booked: %s | held: %s | free: %s%n", String.join(" ", by.get(State.BOOKED)),
                String.join(" ", by.get(State.HELD)), String.join(" ", by.get(State.FREE)));
    }
}