Corporate Flight Bookings

MEDIUM

Description

There are n flights that are labeled from 1 to n.

You are given an array of flight bookings bookings, where bookings[i] = [first_i, last_i, seats_i] represents a booking for flights first_i through last_i (inclusive) with seats_i 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 * 10⁴
1 <= bookings.length <= 2 * 10⁴
bookings[i].length == 3
1 <= first_i <= last_i <= n
1 <= seats_i <= 10⁴

Approaches

Checkout 2 different approaches to solve Corporate Flight Bookings. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation

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 result of size n, initialized to all zeros.
Loop through each booking [first, last, seats] in the bookings array.
For each booking, run a nested loop from i = first to last.
Inside the nested loop, increment result[i-1] by seats. The subtraction of 1 is to convert the 1-based flight number to a 0-based array index.
After iterating through all bookings, the result array contains the final answer.

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 Analysis

Time Complexity: 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 Complexity: O(N), where N is the number of flights. We need an array of size N to store the seat counts.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Corporate Flight Bookings. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Corporate Flight Bookings

Patterns:

Prefix Sum

Data Structures:

Array