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

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

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

 

示例 1：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

 

提示：

  • 1 <= n <= 2 * 104
  • 1 <= bookings.length <= 2 * 104
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 104
Related Topics
  • 数组
  • 前缀和

  • 👍 194
  • 👎 0

    • 题解

    一看题目啊，emmm，这不简单嘛，直接遍历循环套循环，好处理的嘛

    public int[] corpFlightBookings(int[][] bookings, int n) {
    int [] res = new int[n];
    for (int[] booking : bookings) {
        plus(res, booking[0]-1,booking[1]-1,booking[2]);
    }

    return res;
}


public void plus(int[] arr, int start, int end, int count){
    while (start <= end){
        arr[start] += count;
        start++;
    }
}

    你看这不还过了

    解答成功:
执行耗时:879 ms,击败了29.46% 的Java用户
内存消耗:53.5 MB,击败了44.81% 的Java用户

    但是想一下这中间的过程，应该没那么简单。以官方给出的示例来分析

    输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25

    通过分析这份数据我们可以知道，在1航站新增了10名旅客，直到2航站才下机，所以到3航站的时候这10名旅客就不在了。

    2航站有两批数据，一匹是20 一匹是25，一共新增了45名乘客，加上之前1航站的10名乘客一共是有55名。那么在4航站的时候就有20名下机了，而另外25名可以认为直到一个不存在的6才下机或者不处理也可以。

    那么实际的逻辑就应该是在1的位置新增了10，这个10需要再3的位置减去，在2的位置新增了20、25，分别在4位置和不存在6位置减去。

    所以用一个新的数组保存每个的变更情况，如果为0，则说明没有变更，则需要继承前一个位置的值，如果为正则说有净增加，需要由前一个位置的值加上这个值，如果为负数，则说明有净减少，需要由前一个位置的值减去对应的值。

    思路对应代码

    class Solution {

    public int[] corpFlightBookings(int[][] bookings, int n) {
        int [] res = new int[n];
        for (int[] booking : bookings) {
            res[booking[0]-1] += booking[2];
            if (booking[1]<n){
                res[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < res.length; i++) {
            res[i] += res[i-1];
        }
        return res;
    }
}

    提交下，可以，没毛病

    解答成功:         
执行耗时:2 ms,击败了100.00% 的Java用户         
内存消耗:53.3 MB,击败了67.00% 的Java用户