LeetCode 1109 Corporate Flight Bookings

    
        标签：
        
            数组类题目
        
            LeetCode
        
    发布于：2022-02-12 16:35:42
    编辑于：2022-02-12 17:04:00
    浏览量：829

概述

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;
    }
};

Links: leetcode-1109-corporate-flight-bookings