Corporate Flight Bookings
Medium
There are n flights that are labeled from 1 to n. You are given an array of flight bookings bookings, where bookings[i] = [first<sub>i</sub>, last<sub>i</sub>, seats<sub>i</sub>] represents a booking for flights first<sub>i</sub> through last<sub>i</sub> (inclusive) with seats<sub>i</sub> seats reserved for each flight in the range. Return an array answer of length n, where answer[i] is the total number of seats reserved for flight i.
For example:
bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
In this case, the output is [10,55,45,25,25] because:
Flight labels: 1 2 3 4 5 Booking 1 reserved: 10 10 Booking 2 reserved: 20 20 Booking 3 reserved: 25 25 25 25 Total seats: 10 55 45 25 25
Another example:
bookings = [[1,2,10],[2,2,15]], n = 2
The output is [10,25] because:
Flight labels: 1 2 Booking 1 reserved: 10 10 Booking 2 reserved: 15 Total seats: 10 25
Write an efficient algorithm to solve this problem.
Solution
Naive Solution
The most straightforward approach is to iterate through each booking and update the corresponding flights with the reserved seats. For each booking [first, last, seats], we iterate from first to last (inclusive) and add seats to the answer array at the corresponding index.
Code
def naive_corpFlightBookings(bookings, n):
answer = [0] * n
for first, last, seats in bookings:
for i in range(first - 1, last):
answer[i] += seats
return answer
Time Complexity
O(m * k), where m is the number of bookings and k is the average range size (last - first) for each booking. In the worst case, k can be equal to n, so the complexity becomes O(m * n).
Space Complexity
O(n), as we need to store the answer array of size n.
Optimal Solution: Difference Array
A more efficient approach uses the difference array technique. Instead of directly updating the answer array for each booking, we update only the start and end indices of the booking range. Specifically, for a booking [first, last, seats], we add seats to answer[first - 1] and subtract seats from answer[last] (if last is within the bounds of the array). After processing all bookings, we compute the prefix sum of the answer array to get the final result.
Code
def corpFlightBookings(bookings, n):
answer = [0] * n
for first, last, seats in bookings:
answer[first - 1] += seats
if last < n:
answer[last] -= seats
for i in range(1, n):
answer[i] += answer[i - 1]
return answer
Time Complexity
O(m + n), where m is the number of bookings and n is the number of flights. We iterate through the bookings once (O(m)) and then compute the prefix sum (O(n)).
Space Complexity
O(n), as we need to store the answer array of size n.
Edge Cases
- Empty Bookings: If the
bookingsarray is empty, the function should return an array of zeros of lengthn. - Invalid Booking Ranges: If a booking has
first > last, it should be handled gracefully (e.g., by skipping the booking). - Large Number of Bookings: The solution should be efficient enough to handle a large number of bookings without exceeding time limits.
- Single Flight Bookings: Bookings where
first == lastshould be handled correctly.
Example
bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]]
n = 5
Using the optimal solution:
1. Initialize answer = [0, 0, 0, 0, 0]
2. Process [1, 2, 10]: answer[0] += 10, answer[2] -= 10 => answer = [10, 0, -10, 0, 0]
3. Process [2, 3, 20]: answer[1] += 20, answer[3] -= 20 => answer = [10, 20, -10, -20, 0]
4. Process [2, 5, 25]: answer[1] += 25, answer[5] -= 25 => answer = [10, 45, -10, -20, -25] (answer[5] ignored)
5. Compute prefix sum: answer = [10, 55, 45, 25, 0]
