There are n
flights, and they are labeled from 1
to n
.
We have a list of flight bookings. The i
-th booking bookings[i] = [i, j, k]
means that we booked k
seats from flights labeled i
to j
inclusive.
Return an array answer
of length n
, representing the number of seats booked on each flight in order of their label.
Example 1:
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 Output: [10,55,45,25,25]
Constraints:
1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000
Solution: Marking start and end
Time complexity: O(|bookings|)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) { vector<int> ans(n + 1); for (const auto& b : bookings) { ans[b[0] - 1] += b[2]; ans[b[1]] -= b[2]; } for (int i = 1; i < n; ++i) ans[i] += ans[i - 1]; ans.pop_back(); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment