LeetCode 1109 Corporate Flight Bookings
概述
https://leetcode.com/problems/corporate-flight-bookings/
暴力法
时间复杂度 O(n^2),TLE 了。
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> ans(n, 0);
for (auto& b : bookings) {
for (int i = b[0] - 1; i <= b[1] - 1; i ++) {
ans[i] += b[2];
}
}
return ans;
}
};
差分数组
注意到这里都是按范围预约的航班,我们既然不能暴力遍历,就得想一下如何利用范围构造某种数据结构。
我们的差分数组里存的范围都是从 0 开始的。
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> diff(n, 0);
for (auto& b : bookings) {
diff[b[1] - 1] += b[2];
if (b[0] - 2 >= 0) diff[b[0] - 2] -= b[2];
}
vector<int> ans(n, 0);
int sum = 0;
for (int i = n - 1; i >= 0; i --) {
ans[i] = diff[i] + sum;
sum += diff[i];
}
return ans;
}
};