admin管理员组文章数量:1616033
题 : https://leetcode/problems/corporate-flight-bookings/
题目大意
n个航班,有1 到 n 标示。
一种预定位置的格式是 bookings[p] = [i, j, k],意味着 第p个订单是预定 第i 至 j 航班中每个航班 k 个位置。
输出各航班被预定位置的数量。
思路
观察限制条件,若暴力,每个航班去查所有订单 时间复杂度为 O(bookings.length * n)
1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000
借助差分的思想,设 第 x 个航班,航班售票为y。
那么可以将整个 航班售票情况 视为 一个离散点组成的直方图。
对于一个booking[p] = [ i, j, k],看作在 i 位置的增加 k,在 j + 1位置减少了k。
具体操作
1.遍历每个booking = [ i, j, k] ,将arr[i - 1] += k (增长的趋势),arr[j] -= k (下降的趋势)。构建 booking 所有位置的差分关系。这arr[i] 表明了,第i位置的高度比 第i-1位置的高度高多少。
2.从 i = 1,依次计算出 arr[i] += arr[i-1] 。
时间复杂度 O(bookings.length + n))
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 < n; i++) {
res[i] += res[i - 1];
}
return res;
}
}
本文标签: LeetCodeCorporateBookingsFlight
版权声明:本文标题:[LeetCode] 1109. Corporate Flight Bookings 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728724824a1170608.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论