本题的区间上的预定记录可以看做是对这个区间施加的增量
对于一个差分数组，对[l, r]区间施加增量inc后，d[l]增加inc，而d[r + 1]减少inc。
由此便可以通过原预定记录重构出差分数组，最后进行前缀和求值就是所得结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> ret(n, 0);
for(auto& booking : bookings)
{
ret[booking[0] - 1] += booking[2];
if(booking[1] < n)
ret[booking[1]] -= booking[2];
}
for(int i = 1; i < n; ++i)
ret[i] += ret[i - 1];
return ret;
}
};
|