1109. Corporate Flight Bookings

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation