OA: Parking garage with fees and reservations

Implement ParkingGarage(small: int, medium: int, large: int): a garage with that many spots of each size. Spots are named by size letter and number: "S1"…"S<small>", "M1"…, "L1"…. Every method takes a timestamp first (whole minutes). Timestamps never decrease from one call to the next (two calls may share one).

A vehicle is a "motorcycle" (fits any spot), a "car" (fits medium or large) or a "van" (large only). Vehicles are identified by their plate.

• park(timestamp, plate, vehicle) -> str | None: park in the smallest size that fits and has a free spot, and within that size the lowest-numbered free spot. Return the spot. None (changing nothing) if that plate is already parked or no fitting spot is free.
• leave(timestamp, plate) -> str | None: the vehicle leaves and its spot becomes free. Return the spot, or None if that plate isn't parked.
• find_vehicle(timestamp, plate) -> str | None: the spot it's parked in, or None.
• free_spots(timestamp, size) -> int: how many spots of that size ("small", "medium" or "large") are free.

g = ParkingGarage(1, 1, 2)
g.park(0, "BIKE1", "motorcycle")   # "S1"
g.park(1, "BIKE2", "motorcycle")   # "M1": small is full, so the next size up
g.park(2, "CAR1", "car")           # "L1"
g.park(3, "VAN1", "van")           # "L2"
g.park(4, "VAN2", "van")           # None: no large spot left
g.park(5, "CAR1", "car")           # None: already parked
g.leave(6, "BIKE2")                # "M1"
g.park(7, "CAR2", "car")           # "M1"
g.leave(8, "CAR1")                 # "L1"
g.park(9, "VAN2", "van")           # "L1": the lowest-numbered free spot
g.free_spots(10, "large")          # 0
g.find_vehicle(11, "VAN1")         # "L2"

Constraints

• Up to 5 * 10^4 spots of each size and about 2 * 10^5 calls.
• Aim for O(log n) per park and leave, and O(1) for find_vehicle and free_spots.