# Corporate Flight Bookings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/corporate-flight-bookings)
Canonical: https://scaleengineer.com/dsa/problems/corporate-flight-bookings
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
There are `n` flights that are labeled from `1` to `n`.

You are given an array of flight bookings `bookings`, where `bookings[i] = [firsti, lasti, seatsi]` represents a booking for flights `firsti` through `lasti` (**inclusive**) with `seatsi` 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 * 104`
* `1 <= bookings.length <= 2 * 104`
* `bookings[i].length == 3`
* `1 <= firsti <= lasti <= n`
* `1 <= seatsi <= 104`

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

```java
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;
    }
}
```
### 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.

## Difference Array and Prefix Sum
A more efficient approach uses the concept of a difference array. Instead of updating every flight in a range for each booking, we only mark the changes at the start and end of the range. A single pass at the end is then used to calculate the final seat counts for all flights.
**Time:** O(N + M), where N is the number of flights and M is the number of bookings. We iterate through the M bookings once to populate the difference array (O(M)), and then iterate through the N flights once to compute the prefix sum (O(N)). · **Space:** O(N), where N is the number of flights. We use an array of size N to store the differences and then the final results.
**Pros:** Highly efficient with linear time complexity.; Scales well with large inputs and avoids TLE.
**Cons:** Slightly more complex to understand than the brute-force approach.
### Explanation
This technique is ideal for problems involving multiple range updates. The core idea is that a booking `[first, last, seats]` increases the seat count by `seats` for all flights from `first` onwards, and this effect is canceled out from flight `last + 1` onwards.

We can represent this with just two operations: add `seats` at the start index (`first - 1`) and subtract `seats` at the index right after the end of the range (`last`). After processing all such updates for every booking, the array contains the net change at each flight index. The actual value at any index `i` is the sum of all changes up to that index (a prefix sum). By iterating through the array once more and accumulating the values, we can find the final seat count for each flight.

```java
class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] result = new int[n];
        
        // Step 1: Apply the changes to the difference array
        for (int[] booking : bookings) {
            int first = booking[0];
            int last = booking[1];
            int seats = booking[2];
            
            // Add seats at the start of the range (0-indexed)
            result[first - 1] += seats;
            
            // Subtract seats at the position after the end of the range
            // if it's within the bounds of the array
            if (last < n) {
                result[last] -= seats;
            }
        }
        
        // Step 2: Compute the prefix sum to get the final result
        for (int i = 1; i < n; i++) {
            result[i] += result[i - 1];
        }
        
        return result;
    }
}
```
### Algorithm
- Create an integer array `result` of size `n`, initialized to all zeros. This array will first serve as our difference array.
- Iterate through each booking `[first, last, seats]`.
- For each booking, add `seats` to `result[first - 1]`. This marks the start of the range where seats are added.
- If `last` is less than `n`, subtract `seats` from `result[last]`. This marks the point where the added seats are 'canceled out' for subsequent flights.
- After processing all bookings, the `result` array holds the differences. Now, convert it into a prefix sum array.
- Iterate from the second element (`i = 1`) to the end of the `result` array. Update each element `result[i]` by adding the previous element: `result[i] += result[i-1]`.
- The modified `result` array is the final answer.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number[][]} bookings * @param {number} n * @return {number[]} */ var corpFlightBookings =
  function (bookings, n) {
    const ans = new Array(n).fill(0);
    for (const [first, last, seats] of bookings) {
      ans[first - 1] += seats;
      if (last < n) {
        ans[last] -= seats;
      }
    }
    for (let i = 1; i < n; ++i) {
      ans[i] += ans[i - 1];
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> corpFlightBookings(vector<vector<int>> &bookings, int n) {
    vector<int> ans(n);
    for (auto &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;
  }
};

```

### Python

```python
class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]: ans = [0] * n for first, last, seats in bookings: ans[first - 1] += seats if last < n: ans[last] -= seats return list(accumulate(ans))

```