Leftmost-Fit Theater Row Booking With Bulk Cancellation by Group

A single theater row has n seats, numbered 0 to n - 1. Nobody is seated yet. A box-office system then feeds in a sequence of two kinds of requests, and your job is to simulate the row and hand back one outcome per request, in the order the requests came in.

• Book [1, size, group]: scan the row for a run of size seats sitting empty back to back, starting your search from seat 0. The first such run you find (the one whose first seat has the lowest index) gets assigned entirely to group; report that first seat's index as the outcome. If the row has no run that long anywhere, nothing changes and the outcome is -1.
• Cancel [2, group]: clear out every seat group currently occupies, no matter how many separate bookings put them there, and report how many seats came free (0 if group wasn't seated anywhere).

Your function hands back one outcome per request, lined up with the request that produced it.

Function signature

def run_row_bookings(n: int, requests: list[list]) -> list[int]:

Rules

• "Left-most" means: among every block of size consecutive empty seats, pick the one whose first seat has the smallest index. The chosen block doesn't have to be a maximal empty run by itself — it can start partway through a longer one.
• A group can hold several separate blocks at once, from separate bookings made at different times. Cancelling that group releases all of them in one call.
• Booking for a group that already holds seats elsewhere is fine and doesn't touch what it already has.
• After a cancellation, the same group name can book again from scratch.

Example

n = 10
operations = [
    [1, 3, "A"], [1, 2, "B"], [1, 2, "C"], [2, "B"],
    [1, 3, "D"], [1, 2, "E"], [2, "A"], [1, 4, "F"],
]
run_row_bookings(n, operations)
# -> [0, 3, 5, 2, 7, 3, 3, -1]

Group A takes seats 0-2, B takes 3-4, C takes 5-6. Cancelling B frees 2 seats (3-4). The next booking for 3 seats skips the 2-seat gap at 3-4 (too small) and lands at 7 (seats 7-9). A 2-seat booking then fills the 3-4 gap. Cancelling A frees 3 seats (0-2), but nothing in the row ever again has a free run of 4, so the last booking fails with -1.

Constraints

• The row holds somewhere between a single seat and 100,000 seats.
• The request list itself can also run as long as 100,000 entries.
• A booking's requested size never exceeds how many seats the row has.
• Treat group identifiers as opaque, comparable tokens (plain strings work fine).
• Design goal: each request should resolve in time that grows with the logarithm of the row size, not its length; a cancellation is allowed to cost more only in proportion to how many seats it actually hands back. A solution that re-scans every seat on every single request will not keep up once the row and request list both reach their upper limits.