LC-1109. 航班预订统计

  1. 航班预订统计
    这里有 n 个航班,它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ,表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti (包含 firsti 和 lasti )的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer,其中 answer[i] 是航班 i 上预订的座位总数。
解析:
参考:
https://leetcode-cn.com/problems/corporate-flight-bookings/solution/5118_hang-ban-yu-ding-tong-ji-by-user9081a/

这个博主讲的很好,自己来总结一下:
类似于公交车站,每一站都可能会有人上车或者下车,我们只需要知道在那个站点的变化即可,在得到初始人数时候就可以算出到每一站的人数有多少
题中的下标是从1开始,所以在写的时候需要更改一下数组的下标

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n, 0);
        for (auto &k : bookings) {
            diff[k[0] - 1] += k[2];
            if(k[1] < n) {
                diff[k[1]] -= k[2];
            }
        }
        vector<int> ans(n);
        ans[0] = diff[0];
        for (int i = 1; i < n; i++) {
            ans[i] = diff[i] + ans[i - 1];
        }
        return ans;
    }
};
上一篇:动态规划问题(十四)自动换行问题


下一篇:LeetCode刷题之DP算法