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 * 1041 <= bookings.length <= 2 * 104bookings[i].length == 31 <= firsti <= lasti <= n1 <= seatsi <= 104
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
ans = [0] * n
for first, last, seats in bookings:
ans[first - 1] += seats
if last < n:
ans[last] -= seats
return list(accumulate(ans))class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x):
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
tree = BinaryIndexedTree(n)
for first, last, seats in bookings:
tree.update(first, seats)
tree.update(last + 1, -seats)
return [tree.query(i + 1) for i in range(n)]class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] ans = new int[n];
for (var e : bookings) {
int first = e[0], last = e[1], seats = e[2];
ans[first - 1] += seats;
if (last < n) {
ans[last] -= seats;
}
}
for (int i = 1; i < n; ++i) {
ans[i] += ans[i - 1];
}
return ans;
}
}class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
BinaryIndexedTree tree = new BinaryIndexedTree(n);
for (var e : bookings) {
int first =e[0], last = e[1], seats = e[2];
tree.update(first, seats);
tree.update(last + 1, -seats);
}
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
ans[i] = tree.query(i + 1);
}
return ans;
}
}
class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
}
public void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += x & -x;
}
}
public int query(int x) {
int s = 0;
while (x > 0) {
s += c[x];
x -= x & -x;
}
return s;
}
}class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> ans(n);
for (auto& e : bookings) {
int first = e[0], last = e[1], seats = e[2];
ans[first - 1] += seats;
if (last < n) {
ans[last] -= seats;
}
}
for (int i = 1; i < n; ++i) {
ans[i] += ans[i - 1];
}
return ans;
}
};class BinaryIndexedTree {
public:
BinaryIndexedTree(int _n): n(_n), c(_n + 1){}
void update(int x, int delta) {
while (x <= n) {
c[x] += delta;
x += x & -x;
}
}
int query(int x) {
int s = 0;
while (x) {
s += c[x];
x -= x & -x;
}
return s;
}
private:
int n;
vector<int> c;
};
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
BinaryIndexedTree* tree = new BinaryIndexedTree(n);
for (auto& e : bookings) {
int first = e[0], last = e[1], seats = e[2];
tree->update(first, seats);
tree->update(last + 1, -seats);
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[i] = tree->query(i + 1);
}
return ans;
}
};func corpFlightBookings(bookings [][]int, n int) []int {
ans := make([]int, n)
for _, e := range bookings {
first, last, seats := e[0], e[1], e[2]
ans[first-1] += seats
if last < n {
ans[last] -= seats
}
}
for i := 1; i < n; i++ {
ans[i] += ans[i-1]
}
return ans
}type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += x & -x
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= x & -x
}
return s
}
func corpFlightBookings(bookings [][]int, n int) []int {
tree := newBinaryIndexedTree(n)
for _, e := range bookings {
first, last, seats := e[0], e[1], e[2]
tree.update(first, seats)
tree.update(last+1, -seats)
}
ans := make([]int, n)
for i := range ans {
ans[i] = tree.query(i + 1)
}
return ans
}/**
* @param {number[][]} bookings
* @param {number} n
* @return {number[]}
*/
var corpFlightBookings = function (bookings, n) {
const ans = new Array(n).fill(0);
for (const [first, last, seats] of bookings) {
ans[first - 1] += seats;
if (last < n) {
ans[last] -= seats;
}
}
for (let i = 1; i < n; ++i) {
ans[i] += ans[i - 1];
}
return ans;
};