Corporate Flight Bookings
MedPrompt
There are n flights that are labeled from 1 to n.
You are given an array of flight bookings bookings, where bookings[i] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi 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.
Example 1:
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
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
Hence, answer = [10,55,45,25,25]Example 2:
Input: bookings = [[1,2,10],[2,2,15]], n = 2
Output: [10,25]
Explanation:
Flight labels: 1 2
Booking 1 reserved: 10 10
Booking 2 reserved: 15
Total seats: 10 25
Hence, answer = [10,25]
Constraints:
1 <= n <= 2 * 1041 <= bookings.length <= 2 * 104bookings[i].length == 31 <= firsti <= lasti <= n1 <= seatsi <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the booking process. We initialize an array to hold the seat counts for each flight. Then, for every booking, we iterate through the specified range of flights and add the number of seats to each flight in that range.
Algorithm
- Create an integer array
resultof sizen, initialized to all zeros. - Loop through each booking
[first, last, seats]in thebookingsarray. - For each booking, run a nested loop from
i = firsttolast. - Inside the nested loop, increment
result[i-1]byseats. The subtraction of 1 is to convert the 1-based flight number to a 0-based array index. - After iterating through all bookings, the
resultarray contains the final answer.
Walkthrough
The most straightforward way to solve the problem is to follow the description literally. We create an array representing the n flights and for each booking transaction, we iterate over the flights specified in the booking and add the corresponding number of seats. This process is repeated for all bookings.
class Solution { public int[] corpFlightBookings(int[][] bookings, int n) { int[] result = new int[n]; for (int[] booking : bookings) { int first = booking[0]; int last = booking[1]; int seats = booking[2]; // Note: flights are 1-indexed, array is 0-indexed for (int i = first - 1; i < last; i++) { result[i] += seats; } } return result; }}Complexity
Time
O(N * M), where N is the number of flights and M is the number of bookings. For each of the M bookings, we might iterate up to N flights in the worst case (e.g., a booking from flight 1 to N).
Space
O(N), where N is the number of flights. We need an array of size N to store the seat counts.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem statement.
Cons
Inefficient for large inputs, especially when booking ranges are wide.
Likely to cause a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits.
A more efficient approach uses the concept of a difference array. Instead of updating every flight in a range for each booking, we only mark the changes at the start and end of the range. A single pass at the end is then used to calculate the final seat counts for all flights.
Algorithm
- Create an integer array
resultof sizen, initialized to all zeros. This array will first serve as our difference array. - Iterate through each booking
[first, last, seats]. - For each booking, add
seatstoresult[first - 1]. This marks the start of the range where seats are added. - If
lastis less thann, subtractseatsfromresult[last]. This marks the point where the added seats are 'canceled out' for subsequent flights. - After processing all bookings, the
resultarray holds the differences. Now, convert it into a prefix sum array. - Iterate from the second element (
i = 1) to the end of theresultarray. Update each elementresult[i]by adding the previous element:result[i] += result[i-1]. - The modified
resultarray is the final answer.
Walkthrough
This technique is ideal for problems involving multiple range updates. The core idea is that a booking [first, last, seats] increases the seat count by seats for all flights from first onwards, and this effect is canceled out from flight last + 1 onwards.
We can represent this with just two operations: add seats at the start index (first - 1) and subtract seats at the index right after the end of the range (last). After processing all such updates for every booking, the array contains the net change at each flight index. The actual value at any index i is the sum of all changes up to that index (a prefix sum). By iterating through the array once more and accumulating the values, we can find the final seat count for each flight.
class Solution { public int[] corpFlightBookings(int[][] bookings, int n) { int[] result = new int[n]; // Step 1: Apply the changes to the difference array for (int[] booking : bookings) { int first = booking[0]; int last = booking[1]; int seats = booking[2]; // Add seats at the start of the range (0-indexed) result[first - 1] += seats; // Subtract seats at the position after the end of the range // if it's within the bounds of the array if (last < n) { result[last] -= seats; } } // Step 2: Compute the prefix sum to get the final result for (int i = 1; i < n; i++) { result[i] += result[i - 1]; } return result; }}Complexity
Time
O(N + M), where N is the number of flights and M is the number of bookings. We iterate through the M bookings once to populate the difference array (O(M)), and then iterate through the N flights once to compute the prefix sum (O(N)).
Space
O(N), where N is the number of flights. We use an array of size N to store the differences and then the final results.
Trade-offs
Pros
Highly efficient with linear time complexity.
Scales well with large inputs and avoids TLE.
Cons
Slightly more complex to understand than the brute-force approach.
Solutions
Solution
class Solution {public int[] corpFlightBookings(int[][] bookings, int n) { int[] ans = new int[n]; for (var e : bookings) { int first = e[0], last = e[1], seats = e[2]; ans[first - 1] += seats; if (last < n) { ans[last] -= seats; } } for (int i = 1; i < n; ++i) { ans[i] += ans[i - 1]; } return ans; }}/** * @param {number[][]} bookings * @param {number} n * @return {number[]} */ var corpFlightBookings = function (bookings, n) { const ans = new Array(n).fill(0); for (const [first, last, seats] of bookings) { ans[first - 1] += seats; if (last < n) { ans[last] -= seats; } } for (let i = 1; i < n; ++i) { ans[i] += ans[i - 1]; } return ans; };class Solution {public: vector<int> corpFlightBookings(vector<vector<int>> &bookings, int n) { vector<int> ans(n); for (auto &e : bookings) { int first = e[0], last = e[1], seats = e[2]; ans[first - 1] += seats; if (last < n) { ans[last] -= seats; } } for (int i = 1; i < n; ++i) { ans[i] += ans[i - 1]; } return ans; }};class Solution: def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]: ans = [0] * n for first, last, seats in bookings: ans[first - 1] += seats if last < n: ans[last] -= seats return list(accumulate(ans))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.