题目描述

这里有 n 个航班，它们分别从 1 到 n 进行编号。

我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。

请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。

样例

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]

限制

• 1 <= bookings.length <= 20000
• 1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
• 1 <= bookings[i][2] <= 10000

算法

(差分) $O(n + m)$

1. 题目抽象后，就是给定一个初始全 0 的数组，然后每次将区间 [i, j] 统一增加 k，问操作了若干次之后每个位置的值是多少。
2. 这类经典的问题可以采用区间标记的方式解决。将区间 [i, j] 统一增加 k，我们想象成在 i 位置增加 k，在 j + 1 的位置减少 k。
3. 对于每次增加都如此操作，最后每个位置的前缀和就是当前位置最终的值。

时间复杂度

• 每个区间遍历一次，每个位置遍历一次，故时间复杂度为 $O(n + m)$，其中 $n$ 为位置的个数，$m$ 为区间的个数。

空间复杂度

• 记录答案需要 $O(n)$ 的空间。

C++ 代码

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> ans(n, 0);
        for (auto &b : bookings) {
            int l = b[0], r = b[1], x = b[2];
            ans[l - 1] += x;
            if (r < n)
                ans[r] -= x;
        }

        for (int i = 1; i < n; i++)
            ans[i] += ans[i - 1];

        return ans;
    }
};