1109. 航班预订统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。

我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。

请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。

解:这道题用暴力的方法很简单，用一个set按航班号为key存储就好了

下面这种方法，只用了O(N)的复杂度就解决了

首先我们将对一个区间的操作转化为左、右两个端点上的操作

如对于 bookings = [1, ３, 10]　ｎ = 5

我们正常解法为在　１－３位置上各加１如图所示

1109. 航班预订统计

转换为使用端点表示为：从１开始＋10, 从４开始不加，那我们就标记位置１为10，位置4 为 -10如图：

1109. 航班预订统计

在统计时记res[i] = res[i] + res[i - 1] （i > 0）

1109. 航班预订统计

那么对于多个区间，我们只需要叠加起来即可

1109. 航班预订统计

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        int length =bookings.size();
        //tag记录第i个相比i-1的变量
        vector<int> tag(n,0);
        int l=0,r=0,seat=0;
        for(int index=0;index<length;index++)
        {
            //作为下标，减掉1从0开始
            l=bookings[index][0]-1;
            r=bookings[index][1]-1;
            seat=bookings[index][2];
            tag[l]+=seat;
            if(r+1<n)
            {
                tag[r+1]-=seat;
            }
        }

        //这里之后tag表示的就不是差值而是每次相加后的实际值
        //第一个值不算差值么，这个是我写代码时疑惑的地方，想明白后其实第一个值就是差值自身
        for(int index=1;index<n;index++)
        {
            tag[index]+=tag[index-1];
        }
        return tag;
    }
};

原文链接: https://www.cnblogs.com/wangshaowei/p/12398014.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/391288

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

1109. 航班预订统计

相关推荐