Total Reserved Seats per Flight After Many Range Bookings
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
There are `n` flights, numbered `1` to `n`. Each booking reserves the same number of seats on every flight in a consecutive range: a booking `[first, last, seats]` adds `seats` reserved seats to each flight numbered `first` through `last`, inclusive. Given all the bookings, return the total number of reserved seats on each flight.
### Function Signature
```python
def flight_seat_totals(n: int, bookings: list[list[int]]) -> list[int]:
```
### Rules
- `bookings[j] = [first, last, seats]`, and every booking applies to all flights from `first` to `last`, both included.
- Bookings are independent and may overlap; each one adds to every flight in its range.
- Return a list of length `n` whose element at index `i` is the total for flight `i + 1`. A flight with no bookings has total `0`.
### Constraints
- `1 <= n <= 10^5`
- `1 <= len(bookings) <= 10^5`
- `1 <= first <= last <= n`
- `1 <= seats <= 10^4`
- Every total is at most `10^9`, so it fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: n = 5, bookings = [[1, 3, 4], [2, 5, 3], [3, 3, 1]]
Output: [4, 7, 8, 3, 3]
```
Flight 1 gets 4 seats from the first booking. Flight 2 gets 4 + 3 = 7. Flight 3 is covered by all three bookings: 4 + 3 + 1 = 8. Flights 4 and 5 get 3 each from the second booking.
**Example 2**
```text
Input: n = 3, bookings = [[3, 3, 7], [1, 1, 2]]
Output: [2, 0, 7]
```
No booking covers flight 2, so its total is 0.
**Example 3**
```text
Input: n = 4, bookings = [[1, 4, 5], [2, 3, 5]]
Output: [5, 10, 10, 5]
```
Overview: Given n numbered flights and a list of bookings that each reserve a fixed number of seats on every flight in an inclusive range, return the total reserved seats for each flight. It tests handling many overlapping range updates efficiently and producing exact per-flight totals for large inputs.
There are `n` flights, numbered `1` through `n`. You are given a list `bookings`, where each booking `bookings[j] = [first, last, seats]` reserves `seats` seats on every flight numbered `first` through `last`, inclusive.
Bookings are independent and may overlap: each booking adds its `seats` to every flight in its range. Return a list of length `n` whose element at index `i` is the total number of reserved seats on flight `i + 1`. A flight that no booking covers has total `0`.
Implement `flight_seat_totals(n, bookings)`.
**Example 1**
```text
Input: n = 5, bookings = [[1, 3, 4], [2, 5, 3], [3, 3, 1]]
Output: [4, 7, 8, 3, 3]
```
Flight 1 gets 4 seats from the first booking. Flight 2 gets 4 + 3 = 7. Flight 3 is covered by all three bookings: 4 + 3 + 1 = 8. Flights 4 and 5 get 3 each from the second booking.
**Example 2**
```text
Input: n = 3, bookings = [[3, 3, 7], [1, 1, 2]]
Output: [2, 0, 7]
```
No booking covers flight 2, so its total is 0.
**Constraints**
- `1 <= n <= 10^5`
- `1 <= bookings.length <= 10^5`
- `bookings[j] = [first, last, seats]`
- `1 <= first <= last <= n`
- `1 <= seats <= 10^4`
- Every total is at most `10^9`, so it fits in a 32-bit signed integer (it never exceeds 2^31 - 1); `int` is enough in Java and C++.
Constraints
- 1 <= n <= 10^5
- 1 <= bookings.length <= 10^5
- bookings[j] = [first, last, seats]
- 1 <= first <= last <= n
- 1 <= seats <= 10^4
- Every total is at most 10^9, so it fits in a 32-bit signed integer
Examples
Input: (5, [[1, 3, 4], [2, 5, 3], [3, 3, 1]])
Expected Output: [4, 7, 8, 3, 3]
Explanation: Source Example 1: overlapping ranges; flight 3 is covered by all three bookings (4 + 3 + 1 = 8).
Input: (3, [[3, 3, 7], [1, 1, 2]])
Expected Output: [2, 0, 7]
Explanation: Source Example 2: bookings listed out of flight order; flight 2 has no booking and stays 0.
Hints
- Flights are numbered from 1 and each range [first, last] includes both ends, while the returned list is indexed from 0: flight i + 1 sits at index i.
- With up to 10^5 bookings over up to 10^5 flights, visiting every flight of every booking can take about 10^10 steps; look for a way to record each booking in constant time.
- Overlapping bookings simply add together, and a flight that no booking covers reports 0.