# 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_i, last_i, seats_i]</code> represents a booking for flights <code>first_i</code> through <code>last_i</code> ( **inclusive** ) with <code>seats_i</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⁴</code>
- <code>1 <= bookings.length <= 2 * 10⁴</code>
- <code>bookings[i].length == 3</code>
- <code>1 <= first_i <= last_i <= n</code>
- <code>1 <= seats_i <= 10⁴</code>

## Solution 1 - Difference Array

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)類似