Leetcode 1109. Corporate Flight Bookings

Problem Explanation

This problem is about managing flight bookings. We have a total of n flights and they are labelled from 1 to n. The data about the bookings is given in the form of 2D array where each sub-array represents a booking and contains three elements. The first two elements represent the starting and ending flight labels for the booking. They are inclusive which means if the starting flight label is i and ending flight label is j, the seats are booked from flights labelled i to j, both included. The third element represents the number of seats booked. We need to return an array of length n that represents the total number of seats booked on each flight, in the order of their labels.

Let's consider an example for better understanding:

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

In this example, we first book 10 seats from flights 1 to 2. So, the seats booked till now would be [10, 10, 0, 0, 0]. Now, we book 20 seats from flights 2 to 3. So, the seats booked will be updated to [10, 30, 20, 0, 0]. Finally, we book 25 seats from flights 2 to 5. So, the final seats booked will be [10, 55, 45, 25, 25] which is our output.

Approach

This problem can be solved using the prefix sum concept in arrays. We increment the seats booked for the starting index of each booking and decrement the seats after the ending index. Then we go through the array once to calculate the prefix sum which will give us the total seats booked for each flight in the end.

Now, let's go through the solution step-by-step to understand it better.

Python Solution

1
2python
3class Solution:
4    def corpFlightBookings(self, bookings, n):
5        result = [0]*n
6        for i,j,k in bookings:
7            result[i-1] += k
8            if j < n:
9                result[j] -= k
10        for i in range(1, n):
11            result[i] += result[i-1]
12        return result

Java Solution

1
2java
3class Solution {
4    public int[] corpFlightBookings(int[][] bookings, int n) {
5        int[] result = new int[n];
6        for (int[] booking : bookings) {
7            result[booking[0]-1] += booking[2];
8            if (booking[1] < n) {
9                result[booking[1]] -= booking[2];
10            }
11        }
12        for (int i = 1; i < n; i++) {
13            result[i] += result[i-1];
14        }
15        return result;
16    }
17}

JavaScript Solution

1
2javascript
3class Solution {
4    corpFlightBookings(bookings, n) {
5        let result = new Array(n).fill(0);
6        for(let booking of bookings) {
7            result[booking[0]-1] += booking[2];
8            if(booking[1]<n) {
9                result[booking[1]] -= booking[2];
10            }
11        }
12        for(let i=1;i<n;i++){
13            result[i] += result[i-1];
14        }
15        return result;
16    }
17}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
6        vector<int> result(n, 0);
7        for(auto& booking : bookings) {
8            result[booking[0] - 1] += booking[2];
9            if(booking[1] < n) {
10                result[booking[1]] -= booking[2];
11            }
12        }
13        for(int i = 1; i < n; i++) {
14            result[i] += result[i - 1];
15        }
16        return result;
17    }
18};

C# Solution

1
2csharp
3public class Solution {
4    public int[] CorpFlightBookings(int[][] bookings, int n) {
5        int[] result = new int[n];
6        foreach (int[] booking in bookings) {
7            result[booking[0]-1] += booking[2];
8            if (booking[1] < n) {
9                result[booking[1]] -= booking[2];
10            }
11        }
12        for (int i = 1; i < n; i++) {
13            result[i] += result[i-1];
14        }
15        return result;
16    }
17}

These solutions all follow the same procedure. It starts by initializing an array result of length n with all elements set to 0. Then for every booking, it increases the number of seats for the start index by the number of seats booked (k) and decreases the number of seats for the end index+1 by k. In the end, it calculates the prefix sum of the result array and returns that.

This algorithm ensures that for each booking, it correctly increment the number of seats from the start index to the end index (both inclusive). And, when it calculates the prefix sum in the end, it will get the total number of seats booked for every flight.

The time complexity of the solutions is O(n), where n is the number of bookings. Since for every booking, we just perform constant time operations and then do one pass over the result array to calculate the prefix sum. The space complexity is also O(n), for storing the result array.

As you can see, the code is quite straightforward and easy to understand once the solution idea is clear. So this question can be a good practice problem to understand the concept of prefix sum and its usage in solving problems.