{x}
blog image

Corporate Flight Bookings

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 * 104
  • 1 <= bookings.length <= 2 * 104
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 104

Solution Explanation for Corporate Flight Bookings

This problem involves efficiently calculating the total number of seats booked for each flight given a list of bookings. Each booking specifies a range of flights and the number of seats booked for each flight within that range.

Approach 1: Difference Array (Optimal)

This approach leverages the concept of a difference array to achieve linear time complexity. Instead of directly updating the seat counts for each flight in every booking, we use a difference array to track the changes in seat counts.

  1. Initialization: Create an array ans of size n (number of flights), initialized with zeros. This array will store the final seat counts for each flight.

  2. Difference Array Update: For each booking [first, last, seats]:

    • Add seats to ans[first - 1]. This represents the increase in seat count for the starting flight of the booking.
    • If last is not the last flight, subtract seats from ans[last]. This represents the decrease in seat count after the last flight of the booking. This ensures that only flights within the booking range are affected.

  3. Prefix Sum: Finally, compute the prefix sum of the ans array. The prefix sum at index i will then represent the cumulative seat count for flight i.

Time Complexity: O(n), where n is the number of flights. This is because we iterate through the bookings once (O(b), where b is the number of bookings), and then compute the prefix sum in O(n) time. Since b is usually less than or equal to n in practice, the overall complexity is dominated by O(n).

Space Complexity: O(n) to store the ans array.

Approach 2: Binary Indexed Tree (BIT) + Difference Array

This approach uses a Binary Indexed Tree (BIT), also known as a Fenwick tree, to handle the updates and queries more efficiently. It combines the difference array idea with the advantages of a BIT.

  1. Initialization: Create a Binary Indexed Tree (BIT) of size n.

  2. BIT Update: For each booking [first, last, seats]:

    • Add seats to the BIT at index first.
    • Subtract seats from the BIT at index last + 1.

  3. BIT Query: Iterate through flights from 1 to n, and for each flight i, query the BIT for the prefix sum up to i. This gives the total seat count for that flight.

Time Complexity: O(n log n), due to the n queries on the BIT, each taking O(log n) time.

Space Complexity: O(n) to store the BIT.

Note: While the BIT approach has a slightly higher time complexity, it can be advantageous in scenarios with a large number of updates and queries, offering a faster alternative to a simple array-based prefix sum approach. However, for this specific problem, the difference array method is generally preferred for its simplicity and optimal time complexity.

Code Examples (Python3 - Difference Array)

from itertools import accumulate
 
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:  # Avoid index out of bounds
                ans[last] -= seats
        return list(accumulate(ans)) #Efficient prefix sum calculation

This concise Python code efficiently implements the difference array approach using itertools.accumulate for prefix sum calculation. Other languages would follow a similar structure. The BIT implementation is slightly more complex due to the BIT data structure itself.