059. Flight Bookings
Problem
Flights are numbered 1 through n. Each booking (first,last,seats) adds seats to every flight from first through last, inclusive. Return n seat totals in flight order. Bookings have valid one-based endpoints and nonnegative seat counts; n may be zero when there are no bookings.
Examples
Example 1
flight_bookings(5, [(1, 2, 10), (2, 3, 20), (2, 5, 25)])
=> [10, 55, 45, 25, 25]Flight two receives all three bookings.
Example 2
flight_bookings(1, [(1, 1, 7)])
=> [7]Both inclusive endpoints name the same flight.
Example 3
flight_bookings(0, [])
=> []No flights produce no totals.
Reveal the worked solution and reasoning
Why this mechanism works
Translate the business indexing into the established difference-array convention before updating state. Inclusive flights first..last correspond to zero-based cells [first-1,last). That makes last the cancellation boundary without another subtraction or addition.
State and boundaries
difference is indexed by zero-based array boundaries. active is the total booked seats on the current flight.
Protocol
- Allocate n+1 differences.
- Add seats at first-1.
- Subtract seats at last.
- Prefix-sum the first n entries.
- Return per-flight totals.
Visualization
flights 2..4 inclusive
cell indices 1,2,3
boundary range [1,4)Python implementation
def flight_bookings(n, bookings):
difference = [0] * (n + 1)
for first, last, seats in bookings:
difference[first - 1] += seats
difference[last] -= seats
output = []
active = 0
for i in range(n):
active += difference[i]
output.append(active)
return output
Worked execution
flight_bookings(5, [(1, 2, 10), (2, 3, 20), (2, 5, 25)])
L2 flight_bookings: difference = [0] * (n + 1) n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[0, 0, 0, 0, 0, 0] L3 flight_bookings: for first, last, seats in bookings: n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[0, 0, 0, 0, 0, 0]; first=1; last=2; seats=10 L4 flight_bookings: difference[first - 1] += seats n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[10, 0, 0, 0, 0, 0]; first=1; last=2; seats=10 L5 flight_bookings: difference[last] -= seats n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[10, 0, -10, 0, 0, 0]; first=1; last=2; seats=10 L3 flight_bookings: for first, last, seats in bookings: n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[10, 0, -10, 0, 0, 0]; first=2; last=3; seats=20 L4 flight_bookings: difference[first - 1] += seats n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[10, 20, -10, 0, 0, 0]; first=2; last=3; seats=20 L5 flight_bookings: difference[last] -= seats n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[10, 20, -10, -20, 0, 0]; first=2; last=3; seats=20 L3 flight_bookings: for first, last, seats in bookings: n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[10, 20, -10, -20, 0, 0]; first=2; last=5; seats=25 ... 14 intermediate state changes omitted ... L9 flight_bookings: active += difference[i] n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[10, 45, -10, -20, 0, -25]; first=2; last=5; seats=25; output=[10, 55, 45]; active=25; i=3 L10 flight_bookings: output.append(active) n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[10, 45, -10, -20, 0, -25]; first=2; last=5; seats=25; output=[10, 55, 45, 25]; active=25; i=3 L8 flight_bookings: for i in range(n): n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[10, 45, -10, -20, 0, -25]; first=2; last=5; seats=25; output=[10, 55, 45, 25]; active=25; i=4 L10 flight_bookings: output.append(active) n=5; bookings=[(1, 2, 10), (2, 3, 20), (2, 5, 25)]; difference=[10, 45, -10, -20, 0, -25]; first=2; last=5; seats=25; output=[10, 55, 45, 25, 25]; active=25; i=4
Result: [10, 55, 45, 25, 25]. Flight two receives all three bookings.
flight_bookings(1, [(1, 1, 7)])
L2 flight_bookings: difference = [0] * (n + 1) n=1; bookings=[(1, 1, 7)]; difference=[0, 0] L3 flight_bookings: for first, last, seats in bookings: n=1; bookings=[(1, 1, 7)]; difference=[0, 0]; first=1; last=1; seats=7 L4 flight_bookings: difference[first - 1] += seats n=1; bookings=[(1, 1, 7)]; difference=[7, 0]; first=1; last=1; seats=7 L5 flight_bookings: difference[last] -= seats n=1; bookings=[(1, 1, 7)]; difference=[7, -7]; first=1; last=1; seats=7 L6 flight_bookings: output = [] n=1; bookings=[(1, 1, 7)]; difference=[7, -7]; first=1; last=1; seats=7; output=[] L7 flight_bookings: active = 0 n=1; bookings=[(1, 1, 7)]; difference=[7, -7]; first=1; last=1; seats=7; output=[]; active=0 L8 flight_bookings: for i in range(n): n=1; bookings=[(1, 1, 7)]; difference=[7, -7]; first=1; last=1; seats=7; output=[]; active=0; i=0 L9 flight_bookings: active += difference[i] n=1; bookings=[(1, 1, 7)]; difference=[7, -7]; first=1; last=1; seats=7; output=[]; active=7; i=0 L10 flight_bookings: output.append(active) n=1; bookings=[(1, 1, 7)]; difference=[7, -7]; first=1; last=1; seats=7; output=[7]; active=7; i=0
Result: [7]. Both inclusive endpoints name the same flight.
Why the solution is correct
The translated half-open cell range includes exactly the named flights. Each booking activates at the first included cell and cancels just after the last included cell, so integration accumulates precisely the bookings covering each flight.
Time and space
O(n+b) time and O(n) space for b bookings.
Common mistakes
Subtracting at last-1 removes seats from the final included flight. Mixing flight numbers with cell indices causes endpoint errors.
Reasoning card
State: difference is indexed by zero-based array boundaries. active is the total booked seats on the current flight.
Invariant: The running sum is total seats booked on the current flight.
Decision to rehearse: Translate inclusive ranges into start +delta and after-end -delta.
Finish: Return per-flight totals
Transfer exercise
Apply the same endpoint translation to inclusive date ranges after mapping dates to consecutive day indices.