101. Seat Bookings
A regional airline runs a chain of n numbered flights, labelled 1 to n. A group booking [x, y, s] reserves s seats on every flight from number x to number y, inclusive. The two flight numbers may be listed in either order, so the booking covers flights from min(x, y) to max(x, y).
Given all bookings in bookings, return an array answer of length n where answer[i] is the total number of seats reserved on flight i + 1. The bookings list can be empty.
Example 1
- Input:
- bookings = [[1,3,4],[2,4,1]], n = 5
- Output:
- [4,5,5,1,0]
- Explanation:
Flights 1 to 3 get 4 seats each and flights 2 to 4 get 1 more each, giving [4, 5, 5, 1, 0].
Example 2
- Input:
- bookings = [[4,2,6]], n = 4
- Output:
- [0,6,6,6]
- Explanation:
The booking covers flights 2 to 4 (endpoints reversed) with 6 seats, and flight 1 is untouched, giving [0, 6, 6, 6].
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ bookings.length ≤ 100000
- bookings[i].length == 3
- 1 ≤ bookings[i][0], bookings[i][1] ≤ n
- 1 ≤ bookings[i][2] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n)