admin管理员组文章数量:1616033
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
running sum，也叫扫描线，重点在于一个interval有一个值的情况下，我们只看变化的index和变化值，最后叠加就是最终答案。
Intuition
Since ranges are continuous, what if we add reservations to the first flight in the range, and remove them after the last flight in range? We can then use the running sum to update reservations for all flights.
This picture shows the logic for this test case: [[1,2,10],[2,3,20],[3,5,25]].
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] res = new int[n];
for (int[] v : bookings) {
res[v[0] - 1] += v[2];
if (v[1] < n) res[v[1]] -= v[2];
}
for (int i = 1; i < n; ++i) res[i] += res[i - 1];
return res;
}
版权声明：本文标题：1109. Corporate Flight Bookings 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dianzi/1728724784a1170604.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论