Leetcode 1109: Corporate Flight Bookings

Input: You are given a list of bookings, where each element `bookings[i]` is an array containing three integers: `[firsti, lasti, seatsi]`, representing the first flight, last flight, and the number of seats reserved for each flight in the given range. Additionally, you are given an integer `n` representing the total number of flights.

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

Constraints:

• 1 <= n <= 2 * 10^4

• 1 <= bookings.length <= 2 * 10^4

• bookings[i].length == 3

• 1 <= firsti <= lasti <= n

• 1 <= seatsi <= 10^4

Output: Return an array `answer` of length `n`, where each element `answer[i]` represents the total number of seats reserved for the i-th flight.

Example: Output: [10, 55, 45, 25, 25]

Constraints:

• Each element in the answer array should be the sum of reserved seats for the respective flight.

Goal: The goal is to calculate the total number of reserved seats for each flight while efficiently handling multiple bookings that affect overlapping flight ranges.

Steps:

• Start with an array `ans` initialized to zero, which will store the total seats for each flight.

• For each booking, increment the number of seats reserved for the first flight in the range, and decrement the number of seats for the flight right after the last flight in the range.

• Use a cumulative sum to calculate the total seats reserved for each flight.

Goal: Efficient handling of bookings and the large input constraints is crucial to the solution.

Steps:

• Bookings are guaranteed to follow the input constraints, such as 1 <= firsti <= lasti <= n.

Assumptions:

• Each flight range will contain valid indexes and the number of seats will always be within the allowed range.

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

• Explanation: In this case, bookings affect the following flights: the first booking reserves 10 seats for flights 1 and 2. The second booking reserves 20 seats for flights 2 and 3. The third booking reserves 25 seats for flights 2 through 5. The total seats for each flight are: [10, 55, 45, 25, 25].

Approach: We will use a technique known as difference array to efficiently process overlapping bookings and compute the total seats reserved for each flight.

Observations:

• We need to keep track of seat reservations for overlapping flight ranges, which can be handled by using the difference array approach.

• For each booking, we will increment the start of the range and decrement the flight after the last in the range. This way, we can compute the cumulative number of reserved seats with just one pass through the array.

Steps:

• Initialize an array `ans` of size `n` to zero.

• For each booking, update the `ans` array by adding the number of seats to the `firsti - 1` index and subtracting the number of seats from the `lasti` index if `lasti` is less than `n`.

• After all bookings are processed, iterate through the array `ans` and compute the cumulative sum to get the total seats reserved for each flight.

Empty Inputs:

• Bookings array cannot be empty as the problem guarantees at least one booking.

Large Inputs:

• The solution must handle the upper limits of input sizes efficiently (up to 20,000 flights and bookings).

Special Values:

• If all bookings affect the same flight range, the result should correctly accumulate the reserved seats for each flight.

Constraints:

• Ensure the solution works within the provided constraints of `n` and the size of the bookings array.

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int m) {

    vector<int> ans(m, 0);
    for(auto& v: bookings) {
        ans[v[0] - 1] += v[2];
        if(v[1] < m) ans[v[1]] -= v[2];
    }

    for(int j = 1; j < m; j++)
        ans[j] += ans[j-1];

    return ans;
}

1 : Function Declaration

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int m) {

The function `corpFlightBookings` accepts a 2D vector `bookings` representing the booking ranges (start and end flight) and an integer `m` representing the total number of flights. It returns a vector of integers where each element corresponds to the number of bookings for a flight.

2 : Initialization

    vector<int> ans(m, 0);

A vector `ans` of size `m` is initialized to zero, representing the number of bookings for each flight initially set to zero.

3 : Loop Through Bookings

    for(auto& v: bookings) {

This loop iterates over each booking in the `bookings` vector. Each booking is represented by a vector `v` of three elements: start flight, end flight, and number of seats booked.

4 : Booking Updates

        ans[v[0] - 1] += v[2];

For each booking, the number of seats booked is added to the `ans` vector at the index corresponding to the start flight (adjusted by subtracting 1 for zero-based indexing).

5 : Decrement After End Flight

        if(v[1] < m) ans[v[1]] -= v[2];

If the end flight `v[1]` is less than `m` (i.e., within the range of flights), the number of seats booked is subtracted from the `ans` vector at the index corresponding to the end flight.

6 : Prefix Sum Calculation

    for(int j = 1; j < m; j++)

This loop calculates the prefix sum for each flight, adding the number of seats booked for each previous flight to compute the total number of seats for the current flight.

7 : Prefix Sum Update

        ans[j] += ans[j-1];

The prefix sum is updated for each flight by adding the previous flight's seat count to the current flight's seat count.

8 : Return Statement

    return ans;

The function returns the `ans` vector, which contains the total number of seats booked for each flight after processing all bookings.

Best Case: O(n + m)

Average Case: O(n + m)

Worst Case: O(n + m)

Description: The time complexity is O(n + m), where `n` is the number of flights and `m` is the number of bookings, as we process each booking and then compute the cumulative sum for the flights.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n), where `n` is the number of flights, due to the array used to store seat reservations for each flight.

Leetcode 1109: Corporate Flight Bookings

Explore →