---
# System prepended metadata

title: LC 1109. Corporate Flight Bookings
tags: [medium, leedcode, Difference Array, python]

---

# LC 1109. Corporate Flight Bookings

### [Problem link](https://leetcode.com/problems/corporate-flight-bookings/)

###### tags: `leedcode` `python` `medium` `Difference Array`

There are <code>n</code> flights that are labeled from <code>1</code> to <code>n</code>.

You are given an array of flight bookings <code>bookings</code>, where <code>bookings[i] = [first<sub>i</sub>, last<sub>i</sub>, seats<sub>i</sub>]</code> represents a booking for flights <code>first<sub>i</sub></code> through <code>last<sub>i</sub></code> ( **inclusive** ) with <code>seats<sub>i</sub></code> seats reserved for  **each flight**  in the range.

Return an array <code>answer</code> of length <code>n</code>, where <code>answer[i]</code> is the total number of seats reserved for flight <code>i</code>.

**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:** 

- <code>1 <= n <= 2 * 10<sup>4</sup></code>
- <code>1 <= bookings.length <= 2 * 10<sup>4</sup></code>
- <code>bookings[i].length == 3</code>
- <code>1 <= first<sub>i</sub> <= last<sub>i</sub> <= n</code>
- <code>1 <= seats<sub>i</sub> <= 10<sup>4</sup></code>

## Solution 1 - Difference Array
```python=
class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0] * (n + 1)

        for first, last, seats in bookings:
            diff[first - 1] += seats
            diff[last] -= seats

        res = [0] * n
        res[0] = diff[0]
        for i in range(1, n):
            res[i] = res[i - 1] + diff[i]

        return res
```

>### Complexity
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(n)            | O(n)             |


## Note
與[LC 2772. Apply Operations to Make All Array Elements Equal to Zero](https://hackmd.io/@Alone0506/HJvFoeiYh)類似
