Problem Description

The Corporate Flight Bookings problem asks you to efficiently process a list of flight bookings and determine how many seats are reserved for each flight.

You are given:

• An integer n representing the number of flights, labeled from 1 to n.
• A list bookings where each booking is a list/array of three integers: [first, last, seats]. This means seats seats are booked for every flight from first to last (inclusive).

• 1 ≤ n ≤ 2 * 10⁴
• 1 ≤ bookings.length ≤ 2 * 10⁴
• All bookings are valid; 1 ≤ first ≤ last ≤ n
• 1 ≤ seats ≤ 10⁴

• Each booking can affect a range of flights.
• You must efficiently process potentially large input sizes.
• There is always exactly one valid solution for the output.

Thought Process

At first glance, it might seem natural to process each booking by looping over every flight in the booking's range and adding the number of seats. For example, for a booking [2, 4, 10], you might add 10 seats to flights 2, 3, and 4 directly.

However, with large inputs (up to 20,000 flights and bookings), this brute-force approach becomes far too slow, since each booking could require up to O(n) operations, leading to O(n * m) time overall.

The challenge is to find a way to efficiently add the seat counts to ranges of flights, rather than updating each flight individually for every booking. This is where the concept of a difference array comes in handy: it allows us to update ranges in constant time and then compute the final seat counts with a single pass.

Solution Approach

To solve this problem efficiently, we use the difference array technique:

1. Initialize an array: Create an array answer of length n (for flights 1 to n), initialized with zeros.
2. Apply bookings as range updates:
   • For each booking [first, last, seats]:
   • Add seats to answer[first - 1] (since flight numbers are 1-based).
   • Subtract seats from answer[last] (if last is less than n), to mark the end of the range.
3. Build the final result:
   • Iterate through answer and compute the prefix sum. Each position then contains the total seats reserved for that flight.

• By marking the start and end of each booking's range, we ensure that when we sum up the array, each flight gets the correct total seat count from all bookings affecting it.
• This approach reduces the time complexity to O(n + m), which is efficient enough for large inputs.

Example Walkthrough

Let's walk through a sample input:

Input: n = 5, bookings = [[1,2,10], [2,3,20], [2,5,25]]

Step 1: Initialize answer array
answer = [0, 0, 0, 0, 0]

Step 2: Apply bookings as range updates

• Booking [1,2,10]:
• answer[0] += 10 → [10, 0, 0, 0, 0]
• answer[2] -= 10 → [10, 0, -10, 0, 0]
• Booking [2,3,20]:
• answer[1] += 20 → [10, 20, -10, 0, 0]
• answer[3] -= 20 → [10, 20, -10, -20, 0]
• Booking [2,5,25]:
• answer[1] += 25 → [10, 45, -10, -20, 0]
• answer[5] -= 25 (out of bounds, so nothing happens)

• i=0: 10
• i=1: 10+45 = 55
• i=2: 55+(-10) = 45
• i=3: 45+(-20) = 25
• i=4: 25+0 = 25

Time and Space Complexity

Brute-force approach:

• For each booking, update every flight in its range: O(m * n) time, where m is the number of bookings and n is the number of flights.
• Space: O(n) for the answer array.

• Each booking is processed in O(1) time (mark start and end), so O(m) for all bookings.
• Prefix sum over n flights: O(n) time.
• Total time: O(m + n)
• Space: O(n) for the answer array.

Summary

The Corporate Flight Bookings problem is a classic example of range update optimization. By using the difference array technique, we efficiently process all bookings and compute the reserved seats for each flight in linear time. This approach is both elegant and practical, transforming what could be a slow, brute-force solution into a fast and scalable one. The key insight is to realize that marking the start and end of each booking's range allows us to compute the final seat counts with a simple prefix sum.

Code Implementation

class Solution:
    def corpFlightBookings(self, 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
      

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> answer(n, 0);
        for (const auto& b : bookings) {
            int first = b[0] - 1, last = b[1], seats = b[2];
            answer[first] += seats;
            if (last < n)
                answer[last] -= seats;
        }
        for (int i = 1; i < n; ++i)
            answer[i] += answer[i-1];
        return answer;
    }
};
      

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] answer = new int[n];
        for (int[] b : bookings) {
            int first = b[0] - 1, last = b[1], seats = b[2];
            answer[first] += seats;
            if (last < n)
                answer[last] -= seats;
        }
        for (int i = 1; i < n; i++)
            answer[i] += answer[i-1];
        return answer;
    }
}
      

var corpFlightBookings = function(bookings, n) {
    let answer = new Array(n).fill(0);
    for (let [first, last, seats] of bookings) {
        answer[first - 1] += seats;
        if (last < n)
            answer[last] -= seats;
    }
    for (let i = 1; i < n; ++i)
        answer[i] += answer[i-1];
    return answer;
};