All problems

Corporate Flight Bookings

Medium · prefix sum

A company flies a chain of n flights, numbered from 1 to n. A booking is a list [first, last, seats]: it reserves seats seats on every flight numbered from first to last, both included.

You are given n and the list bookings. Return a list of length n whose entry at index i is the total number of seats reserved on flight i + 1, across all bookings.

Examples

Example 1

Input: n = 5, bookings = [[1, 3, 10], [2, 5, 20]]

Output: [10, 30, 30, 20, 20]

Flight 1 has 10 seats. Flights 2 and 3 have 10 + 20 = 30. Flights 4 and 5 have 20.

Example 2

Input: n = 3, bookings = [[2, 2, 5], [2, 2, 7], [1, 3, 1]]

Output: [1, 13, 1]

Flight 2 is booked three times: 5 + 7 + 1 = 13. Flights 1 and 3 only have the single seat of the last booking.

Example 3

Input: n = 1, bookings = [[1, 1, 4]]

Output: [4]

The only flight has the only booking.

Constraints