Brute Force Solution

A naive approach is to iterate through each booking and, for each booking, iterate through the range of flights it covers, incrementing the seat count for each flight within that range.

Code

def corpFlightBookings_brute_force(bookings, n):
    answer = [0] * n
    for first, last, seats in bookings:
        for i in range(first - 1, last):
            answer[i] += seats
    return answer

Time Complexity

O(m*n), where m is the number of bookings and n is the number of flights. This is because, in the worst case, each booking could span almost all flights, leading to nested loops.

Space Complexity

O(n), where n is the number of flights. This is due to the answer array used to store the seat counts for each flight.

Optimal Solution

A more efficient approach uses the prefix sum technique. Instead of iterating through the range of flights for each booking, we can update the start and end points of the range and then compute the prefix sum to get the final answer.

1. For each booking [first, last, seats], add seats to the first flight and subtract seats from the last + 1 flight (if last + 1 is within the bounds).
2. Compute the prefix sum of the array to get the total seats for each flight.

Code

def corpFlightBookings_optimal(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

Time Complexity

O(m + n), where m is the number of bookings and n is the number of flights. This is because we iterate through the bookings once (O(m)) and then iterate through the flights once to compute the prefix sum (O(n)).

Space Complexity

O(n), where n is the number of flights. This is due to the answer array used to store the seat counts for each flight.

Edge Cases

• Empty Bookings: If the bookings array is empty, the function should return an array of zeros.
• Single Flight: If n is 1, the function should return an array with a single element, which is the sum of all seats reserved for that flight.
• Invalid Input: Cases such as first > last are invalid based on the prompt's constraint 1 <= firsti <= lasti <= n. We can assume that such cases will not appear in the input, so we don't need to validate the input.

Example

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

1. Initialize answer = [0, 0, 0, 0, 0]
2. For booking [1, 2, 10]: answer[0] += 10, answer[2] -= 10 (if 2 < 5). answer becomes [10, 0, -10, 0, 0]
3. For booking [2, 3, 20]: answer[1] += 20, answer[3] -= 20 (if 3 < 5). answer becomes [10, 20, -10, -20, 0]
4. For booking [2, 5, 25]: answer[1] += 25, answer[5] -= 25 (if 5 < 5). answer becomes [10, 45, -10, -20, 0]
5. Compute prefix sum: [10, 10+45, 55-10, 45-20, 25+0] = [10, 55, 45, 25, 25]