[LeetCode] 1109. Corporate Flight Bookings

[grandyang]

There are n flights that are labeled from 1 to n.

You are given an array of flight bookings bookings, where bookings[i] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi seats reserved for each flight in the range.

Return *an array  answer  of length  n , where  answer[i]  is the total number of seats reserved for flight *i.

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
Flight labels:        1   2   3   4   5
Booking 1 reserved:  10  10
Booking 2 reserved:      20  20
Booking 3 reserved:      25  25  25  25
Total seats:         10  55  45  25  25
Hence, answer = [10,55,45,25,25]

Example 2:

Input: bookings = [[1,2,10],[2,2,15]], n = 2
Output: [10,25]
Explanation:
Flight labels:        1   2
Booking 1 reserved:  10  10
Booking 2 reserved:      15
Total seats:         10  25
Hence, answer = [10,25]

Constraints:

• 1 <= n <= 2 * 104
• 1 <= bookings.length <= 2 * 104
• bookings[i].length == 3
• 1 <= firsti <= lasti <= n
• 1 <= seatsi <= 104

这道题说是有n个航班，标号从1到n，每次公司可以连续预定多个航班上的座位，用一个三元数组 [i, j, k]，表示分别预定航班i到j上的k个座位，最后问每个航班上总共被预定了多少个座位。博主先试了一下暴力破解，毫无意外的超时了，想想为啥会超时，因为对于每个预定的区间，都遍历一次的话，最终可能达到n的平方级的复杂度。所以就需要想一些节省运算时间的办法，其实这道的解法很巧妙，先来想想，假如只有一个预定，是所有航班上均订k个座位，那么暴力破解的方法就是从1遍历到n，然后每个都加上k，但还有一种方法，就是只在第一天加上k，然后计算累加和数组，这样之后的每一天都会被加上k。如果是预定前一半的航班，那么暴力破解的方法就是从1遍历到 n/2，而这里的做法是在第一个天加上k，在第 n/2 + 1 天减去k，这样再求累加和数组时，后一半的航班就不会加上k了。对于所有的预定都可以采用这种做法，在起始位置加上k，在结束位置加1处减去k，最后再整体算累加和数组，这样就把平方级的时间复杂度缩小到了线性，完美通过 OJ，参见代码如下：

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

Github 同步地址:

#1109

参考资料：

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

https://leetcode.com/problems/corporate-flight-bookings/discuss/328871/C%2B%2BJava-with-picture-O(n)

https://leetcode.com/problems/corporate-flight-bookings/discuss/328856/JavaC%2B%2BPython-Sweep-Line

LeetCode All in One 题目讲解汇总(持续更新中...)