Corporate Flight Bookings

Medium

Asked by:

64 views

Topics:

ArraysArraysArrays

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⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `bookings` array and the value of `n` (the number of flights)?
Can the values in the `bookings` array (i, j, k) be negative, zero, or exceed the flight range (1 to n)?
If a flight has no bookings, should the corresponding element in the result array be 0?
Are the booking ranges (i, j) inclusive or exclusive?
Is there any specific output format for the returned array (e.g., can I modify the input array in place if permitted)?
Can there be overlapping booking ranges in the `bookings` array?
Can `i` ever be greater than `j` in a booking entry?

Brute Force Solution

Approach

The brute force approach to solving the flight booking problem is like manually going through each booking and updating a list of flight seats. We consider each booking one at a time and apply its effect to every flight day covered by that booking. It's a simple but potentially slow method.

Here's how the algorithm would work step-by-step:

Start with a list representing each day's number of available seats, initially all set to zero.
Take the first booking in the list.
For each day covered by this booking (from the booking's start day to its end day), increase the number of seats booked for that day by the number of seats in this booking.
Repeat this process for every booking in the list, one after the other.
After considering all bookings, the list will show the total number of seats booked for each day.

Code Implementation

def corpFlightBookingsBruteForce(bookings, numberOfFlights):
    flightBookings = [0] * numberOfFlights

    # Iterate through each booking in the bookings list
    for booking in bookings:
        firstFlight = booking[0]
        lastFlight = booking[1]
        seatsBooked = booking[2]

        # Iterate through each flight day within the current booking
        # Adjust flight indices to be 0-based
        for flightIndex in range(firstFlight - 1, lastFlight):

            # Update the booking counts for each day of the given booking
            flightBookings[flightIndex] += seatsBooked

    return flightBookings

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each of the 'm' bookings. For each booking, it iterates through a range of flight days. In the worst case, a single booking could cover all 'n' flight days. Therefore, the outer loop runs 'm' times, and the inner loop, in the worst case, runs 'n' times. The total number of operations will approximate n*m, which simplifies to O(n*m), where 'n' is the number of flight days and 'm' is the number of bookings.

Space Complexity

O(N) – The brute force approach initializes a list representing the number of available seats for each day, initially all set to zero. This list has a size directly proportional to the number of days, which we can consider as N. While the algorithm iterates through the bookings, it modifies this list in place; therefore, the dominant space complexity is due to this initial list of size N. No other significant auxiliary data structures are used.

Optimal Solution

Approach

This problem can be efficiently solved using a technique similar to prefix sums, but applied cleverly to booking counts. The core idea is to track the *changes* in the number of booked seats instead of the actual number directly, allowing us to calculate the final bookings very quickly.

Here's how the algorithm would work step-by-step:

Imagine each flight as a point along a line. For each booking, mark the start flight with an increase in the number of booked seats.
Also, for each booking, mark the flight *after* the end flight with a *decrease* in the number of booked seats. This represents the end of the booking range.
Now, go through each flight in order. Keep a running total of the number of booked seats. Each time you reach a new flight, add the change you marked for that flight to your running total.
The running total at each flight now represents the total number of seats booked for that flight. This is because you've accounted for all increases from the start of booking ranges and decreases at the end of booking ranges.
The resulting array contains the number of seats booked for each flight, which solves the problem efficiently.

Code Implementation

def corporate_flight_bookings(bookings, number_of_flights):
    flight_bookings = [0] * number_of_flights

    # Iterate through bookings to mark start and end changes
    for start, end, seats in bookings:
        flight_bookings[start - 1] += seats

        # If end is not the last flight, decrement after the end
        if end < number_of_flights:
            flight_bookings[end] -= seats

    # Accumulate the bookings to determine final state of each flight
    for flight_index in range(1, number_of_flights):
        flight_bookings[flight_index] += flight_bookings[flight_index - 1]

    return flight_bookings

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the bookings array once, which takes O(m) time where m is the number of bookings. Then, it iterates through the flights array once to compute the prefix sum, which takes O(n) time where n is the number of flights. Because we determine runtime complexity using the worst-case scenario, if m is greater than n, then the time complexity would be O(m). Assuming m is reasonably smaller than n (or at most a constant factor of n), the dominant term is O(n) so the overall time complexity is O(n).

Space Complexity

O(N) – The provided solution uses an array to store the changes in booked seats for each flight. The size of this array is determined by the number of flights, which can be represented as N, where N is the total number of flights. Although the bookings array itself is modified in place, the core auxiliary space usage stems from constructing and using an array of size N to accumulate booking changes. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty bookings array	Return an array of zeros with size n (number of flights) because no bookings imply no changes to the initial flight counts.
Bookings array is null	Throw an IllegalArgumentException (or equivalent in the language used) to indicate invalid input, as null bookings are nonsensical.
n (number of flights) is zero or negative	Throw an IllegalArgumentException (or equivalent) as the number of flights must be a positive integer to be meaningful.
A booking has invalid indices (i > j or indices out of range)	Throw an IllegalArgumentException if i > j or if either index is out of the valid range of 1 to n, inclusive.
Large number of flights (large n) combined with many bookings.	The algorithm uses O(n + k) time/space (where k is number of bookings), profile for time efficiency on large datasets.
Bookings overlap significantly and repeatedly.	The difference array approach should efficiently handle overlapping ranges without issues, but could expose integer overflow with very high numbers of overlapping flights, which is handled through 64-bit integers or other techniques.
Bookings with a large value for the number of seats to book.	Ensure the data type used to store the flight counts (e.g., int) can handle the potential sum of seats across all flights and bookings to prevent integer overflow.
Single flight booking requesting a negative number of seats	Throw an IllegalArgumentException, as a negative number of seats to book is not a valid business case.

Empty bookings array

How to Handle:

Return an array of zeros with size n (number of flights) because no bookings imply no changes to the initial flight counts.

Bookings array is null

How to Handle:

Throw an IllegalArgumentException (or equivalent in the language used) to indicate invalid input, as null bookings are nonsensical.

n (number of flights) is zero or negative

How to Handle:

Throw an IllegalArgumentException (or equivalent) as the number of flights must be a positive integer to be meaningful.

A booking has invalid indices (i > j or indices out of range)

How to Handle:

Throw an IllegalArgumentException if i > j or if either index is out of the valid range of 1 to n, inclusive.

Large number of flights (large n) combined with many bookings.

How to Handle:

The algorithm uses O(n + k) time/space (where k is number of bookings), profile for time efficiency on large datasets.

Bookings overlap significantly and repeatedly.

How to Handle:

The difference array approach should efficiently handle overlapping ranges without issues, but could expose integer overflow with very high numbers of overlapping flights, which is handled through 64-bit integers or other techniques.

Bookings with a large value for the number of seats to book.

How to Handle:

Ensure the data type used to store the flight counts (e.g., int) can handle the potential sum of seats across all flights and bookings to prevent integer overflow.

Single flight booking requesting a negative number of seats

How to Handle:

Throw an IllegalArgumentException, as a negative number of seats to book is not a valid business case.