[数据结构与算法]leetcode-每日一题2021.8.31 航班预订统计

题目

https://leetcode-cn.com/problems/corporate-flight-bookings/

我的思路

根据题意初始化航班号数组，写两个循环，第一个循环是对bookings中的每一项进行遍历，第二个循环是从first到last增加seat。但是结果会超时

我的代码

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> v(n);
        for(int i=0;i<bookings.size();i++){
            for(int j=bookings[i][0]-1;j<=bookings[i][1]-1;j++){
                v[j]=v[j]+bookings[i][2];
            }
        }
        return v;
    }
};

题解思路

对差分数组求前缀和就是原数组

假如booking中的一个元素是[first,last,seat]，那么构造差分数组v[first]+=seat，v[last+1]-=seat

题解代码

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> v(n);
        for(int i=0;i<bookings.size();i++){
            v[bookings[i][0]-1]+=bookings[i][2];
            if(bookings[i][1]<n)
                v[bookings[i][1]]-=bookings[i][2];
        }
        for(int i=1;i<n;i++){
            v[i]+=v[i-1];
        }
        return v;
    }
};