Seats per Trip

Medium

A bus company runs trips trips numbered from 1 to trips. Each order orders[i] = [first, last, seats] books seats seats on every trip from first through last inclusive. Return a list of length trips where position i (0-based) holds the total number of seats booked on trip number i + 1. Walking every trip of every order is too slow for long ranges; aim for linear time.

Example 1

orders=[[1, 3, 4], [2, 2, 6], [3, 4, 1]], trips=4 → [4, 10, 5, 1]

Trip 1: 4. Trip 2: 4 + 6 = 10. Trip 3: 4 + 1 = 5. Trip 4: 1.

Example 2

orders=[[2, 2, 7]], trips=3 → [0, 7, 0]

Seats are taken only on the second trip; the others stay at zero.

Constraints

1 ≤ trips ≤ 2·10⁴
1 ≤ len(orders) ≤ 2·10⁴
orders[i].length == 3
1 ≤ first ≤ last ≤ trips
1 ≤ seats ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Prefix Sum

Similar problems

Shortest Stretch to the Goal Medium Product of All the Others Medium Studios for Recording Sessions Medium Longest Run with a Given Sum Medium Batch of Segment Adjustments Medium

Input

orders=[[1, 3, 4], [2, 2, 6], [3, 4, 1]], trips=4

Expected

[4, 10, 5, 1]

Run checks the first 3 tests in your browser. Submit checks all 107 tests on the server, hidden ones included.