Corporate Flight Bookings - Leetcode Solution

The Corporate Flight Bookings problem on LeetCode can be solved using a simple approach of prefix sum. The problem statement is as follows:

There are n flights, and they are labeled from 1 to n. We have a list of flight bookings. Each booking contains three integers, flight[i][0], flight[i][1], flight[i][2] which means that we booked flight[i][0] to flight[i][1] inclusive, with a value of flight[i][2].

Return an array answer of length n, representing the number of seats booked on each flight in order of their label.

To solve this problem, we will first create a prefix sum of the seat bookings. The prefix sum can be defined as follows:

prefix_sum[i] = prefix_sum[i-1] + bookings[i]

We will then use this prefix sum to calculate the seat bookings for each flight.

The solution for this problem in Python is as follows:

def corpFlightBookings(bookings, n): """ :type bookings: List[List[int]] :type n: int :rtype: List[int] """ # Initialize an array of size n with all elements as 0 ans = [0] * n # Calculate the prefix sum for i in range(len(bookings)): ans[bookings[i][0]-1] += bookings[i][2] if bookings[i][1] < n: ans[bookings[i][1]] -= bookings[i][2] # Calculate the seat bookings for i in range(1,n): ans[i] += ans[i-1] return ans

In this solution, we initialize an array of size n with all elements as 0. We then calculate the prefix sum by iterating through the bookings. We add the value of the booking to the starting flight and subtract the value of the booking from the flight after the ending flight, if the ending flight is less than n. Finally, we iterate through the prefix sum and calculate the seat bookings.

This solution has a time complexity of O(n), as we iterate through the bookings and the prefix sum only once. The space complexity is also O(n), as we use an array of size n to store the answer.

1