LeetCode 1109. 航班预订统计（差分思想）
LeetCode 1109. 航班预订统计（差分思想）
Michael阿明
发布于 2020-07-13 15:06:45
发布于 2020-07-13 15:06:45
1. 题目
这里有 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来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/corporate-flight-bookings 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 看数据量这么大，暴力肯定要超时
- 左端点+num，右端点后面-num，中间的状态不变，就省了给每个位置更新的时间
在这里插入图片描述
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> bk(n+2,0);
for(auto& b : bookings)
{
bk[b[0]] += b[2];//左端点+num
bk[b[1]+1] -= b[2];//右端点后面 +num
}
for(int i = 2; i <= n; i++)
bk[i] += bk[i-1];
return vector<int> (bk.begin()+1, bk.end()-1);
}
};344 ms 49.1 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/05/29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
