The problem
A line has n sections, numbered 0 to n - 1. Each trip [l, r, k] is a group of k passengers who ride every section from l to r, both included. Return a list of n numbers: the total number of passengers on each section.
section_loads(6, [[1, 3, 4], [2, 5, 2], [0, 1, 1]])
# [1, 5, 6, 6, 2, 2]
section_loads(4, []) # [0, 0, 0, 0]
Limits
nand the number of trips are each up to 200,000. A single trip can cover the whole line.
Builds on ARRS-4 Prefix sums and difference arrays.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
6 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Three trips | Not run | |
| 2 | No trips | Not run | |
| 3 | A trip to the last section | Not run | |
| 4 | One section | Not run | |
| 5 | Overlapping trips | Not run | |
| 6 | 200,000 long trips | Not run |