Problem Breakdown
We are managing seat reservations for n flights labeled 1 through n. We receive a list of bookings, where each booking specifies an inclusive range [first, last] and the number of seats reserved (seats) for every flight in that range. Our goal is to compute the total accumulated seats reserved for each individual flight after processing all bookings.
Inputs:
bookings: A 2D list (list of lists) where each element[first, last, seats]defines a reservation.n: An integer representing the number of flights.
Outputs:
answer: A list of lengthn, where indexicorresponds to flighti+1. The value is the total seat count for that specific flight.
Constraints & Edge Cases:
- Flights are 1-indexed in input, but we must return a standard Python array (0-indexed). We need to map flight
kto indexk-1. - Ranges can overlap significantly or be disjoint.
- The maximum number of flights and bookings is . A naive simulation iterating through every booking range could result in up to operations, potentially hitting Time Limit Exceeded (TLE). We need an efficient approach for large inputs.
Intuition
If we were to simulate the bookings directly on a frequency array of size n, each booking [first, last] would require iterating from index first-1 to last-1. In the worst case where every flight is booked in every range (e.g., all ranges are 1..N), this results in time complexity. Given constraints of up to for both N and bookings count, , which is risky for Python within typical interview limits (usually ~1-3 seconds).
Key Insight: This problem maps perfectly onto the Difference Array technique. Instead of updating every element in a range, we record changes at specific boundaries:
- Add
seatsto the start index (first - 1). - Subtract
seatsfrom the index immediately following the end (last).
By doing this for all bookings and then computing the prefix sum (cumulative sum) of the array once, we recover the actual seat counts at each flight efficiently. This transforms range updates into operations per booking.
Approach
- Initialize a Difference Array: Create an integer list
diffof sizen + 2. We usen + 2to safely handle the subtraction logic without boundary checks (specifically when a booking ends at flightn, we need indexn+1or simply ensure array is large enough).- For each booking
[first, last, seats]:- Increment
diff[first - 1] += seats. - Decrement
diff[last] -= seats. Note: Since flights are up ton, the subtraction happens at indexlast(which corresponds to flightlast+1). If we allocate sizen + 2, indices go up ton + 1. This covers all cases safely.
- Increment
- For each booking
- Compute Prefix Sums: Iterate through the difference array from index 0 to
n - 1. Maintain a running sum (current_seats) and update it by adding the current value indiff[i]. Store this cumulative total into our result list (or overwritediffif we don’t need original values). - Return Result: Return the first
nelements of the computed array, which represent flights 1 throughn.
Complexity Analysis
- Time Complexity: , where is the number of flights and is the length of
bookings. We iterate once over bookings () to apply difference updates, then iterate once over the array size () to compute prefix sums. This fits well within limits for . - Space Complexity: to store the result/difference array. We do not use extra space proportional to input bookings beyond this constant-size auxiliary structure (excluding output).
Solution
def corpFlightBookings(bookings: list[list[int]], n: int) -> list[int]:
# Initialize difference array with size n + 2 to handle boundary conditions easily.
# Index i corresponds to flight i+1.
# We need index 'last' for subtraction, so if last=n (flight), we access index n.
diff = [0] * (n + 2)
# Apply difference array updates: O(K) where K is len(bookings)
for first, last, seats in bookings:
diff[first - 1] += seats # Add to start of range
diff[last] -= seats # Subtract after end of range (inclusive logic handled by index offset)
result = []
current_seats = 0
# Compute prefix sums and build the final answer array: O(N)
for i in range(n):
current_seats += diff[i]
result.append(current_seats)
return result
Edge Cases Handled
- Full Range Booking: A booking covering
[1, n]increments index