Formatted question description: https://leetcode.ca/all/1109.html

# 1109. Corporate Flight Bookings (Medium)

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] <= bookings[i] <= n <= 20000
• 1 <= bookings[i] <= 10000

Related Topics:
Array, Math

## Solution 1. Heap

// OJ: https://leetcode.com/problems/corporate-flight-bookings/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& A, int n) {
vector<int> ans(n);
sort(begin(A), end(A));
auto cmp = [&](int a, int b) { return A[a] > A[b]; };
priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
for (int i = 0, j = 0, sum = 0; i < n; ++i) {
while (q.size() && A[q.top()] < i + 1) {
sum -= A[q.top()];
q.pop();
}
while (j < A.size() && A[j] <= i + 1 && A[j] >= i + 1) {
q.push(j);
sum += A[j++];
}
ans[i] = sum;
}
return ans;
}
};


## Solution 2. Diff Array

// OJ: https://leetcode.com/problems/corporate-flight-bookings/
// Time: O(N)
// Space: O(1)
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& A, int n) {
vector<int> ans(n);
for (auto &v : A) {
ans[v - 1] += v;
if (v < n) ans[v] -= v;
}
for (int i = 1; i < n; ++i) ans[i] += ans[i - 1];
return ans;
}
};


Java

• class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] seats = new int[n];
for (int[] booking : bookings) {
int start = booking, end = booking, count = booking;
seats[start - 1] += count;
if (end < n)
seats[end] -= count;
}
for (int i = 1; i < n; i++)
seats[i] += seats[i - 1];
return seats;
}
}

• // OJ: https://leetcode.com/problems/corporate-flight-bookings/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& A, int n) {
vector<int> ans(n);
sort(begin(A), end(A));
auto cmp = [&](int a, int b) { return A[a] > A[b]; };
priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
for (int i = 0, j = 0, sum = 0; i < n; ++i) {
while (q.size() && A[q.top()] < i + 1) {
sum -= A[q.top()];
q.pop();
}
while (j < A.size() && A[j] <= i + 1 && A[j] >= i + 1) {
q.push(j);
sum += A[j++];
}
ans[i] = sum;
}
return ans;
}
};

• # 1109. Corporate Flight Bookings
# https://leetcode.com/problems/corporate-flight-bookings/

class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
res =  * (n + 1)

for start,end,seats in bookings:
res[start - 1] += seats
res[end] -= seats

for i in range(1, n):
res[i] += res[i - 1]

return res[:-1]