题目
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 \(bookings[i] = [first_i, last_i, seats_i]\) 意味着在从 \(first_i\) 到 \(last_i\) （包含 \(first_i\) 和 \(last_i\)）的 每个航班 上预订了 \(seats_i\) 个座位。
请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。
示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]
示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号 1 2
预订记录 1 ： 10 10
预订记录 2 ： 15
总座位数： 10 25
因此，answer = [10,25]
提示：
- \(1 <= n <= 2 * 10^4\)
- \(1 <= bookings.length <= 2 * 10^4\)
- \(bookings[i].length == 3\)
- 1 <= \(first_i\) <= \(last_i\) <= n
- \(1 <= seats_i <= 10^4\)
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/corporate-flight-bookings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
一开始想用暴力法先过，不出意外超时了，因为在极端情况下时间复杂度可以达到\(O(n^2)\)。这题其实可以用公交车站上下人的思路来做，把预订表中的\(first_i\)看作乘客上车车站，\(last_i + 1\)看作乘客下车车站，\(seats_i\)看作上车人数，用一个数组来记录上下车的车站和人数，因为预订表中的航班是从1开始算的，在记录时将\(first_i - 1\)处加上\(seats_i\)，在\(last_i\)处减去\(seats_i\)（注意最后一站不用减）。最后计算上面数组的前缀和就能得到每一站车上的乘客人数（即每个航班上预订的座位总数）。
时间复杂度O(n + m)，空间复杂度O(1)。返回数组不计入空间复杂度。
代码
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> ans(n);
for(const auto& booking : bookings)
{
ans[booking[0] - 1] += booking[2];
if(booking[1] < n) ans[booking[1]] -= booking[2];
}
for(int i = 1; i < n; ++i)
{
ans[i] += ans[i - 1];
}
return ans;
}
};