这里有 n 个航班，它们分别从 1 到 n 进行编号。
我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。
请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。
解:这道题用暴力的方法很简单，用一个set按航班号为key存储就好了
下面这种方法，只用了O(N)的复杂度就解决了
首先我们将对一个区间的操作转化为左、右两个端点上的操作
如对于 bookings = [1, ３, 10] ｎ = 5
我们正常解法为在 １－３ 位置上各加１如图所示
转换为使用端点表示为：从１开始＋10, 从４开始不加，那我们就标记位置１为10，位置4 为 -10如图：
在统计时 记res[i] = res[i] + res[i – 1] （i > 0）
那么对于 多个区间，我们只需要叠加起来即可
class Solution { public: vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) { int length =bookings.size(); //tag记录第i个相比i-1的变量 vector<int> tag(n,0); int l=0,r=0,seat=0; for(int index=0;index<length;index++) { //作为下标，减掉1从0开始 l=bookings[index][0]-1; r=bookings[index][1]-1; seat=bookings[index][2]; tag[l]+=seat; if(r+1<n) { tag[r+1]-=seat; } } //这里之后tag表示的就不是差值而是每次相加后的实际值 //第一个值不算差值么，这个是我写代码时疑惑的地方，想明白后其实第一个值就是差值自身 for(int index=1;index<n;index++) { tag[index]+=tag[index-1]; } return tag; } };
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/17563.html