Loading page…
Practice problem · medium
A parcel-delivery app sends courier bikes along a one-lane road to a depot. Bike i starts at distance positions[i] from the start of the road and rides at a steady speed speeds[i]. The depot is at distance target.
Nobody can overtake. When a faster bike catches a slower one, it slows down and rides right behind it, and they arrive as one convoy. A bike that reaches the depot at the same moment as the bike ahead is part of its convoy.
Write convoy_count(target, positions, speeds).
target.Input: target = 12, positions = [10, 8, 0, 5, 3], speeds = [2, 4, 1, 1, 3]
Output: 3Go from the bike closest to the depot back to the one furthest away. A bike joins the convoy ahead when it would arrive no later than that convoy.
| Position | Speed | Minutes to the depot alone | Convoy ahead arrives | Result |
|---|---|---|---|---|
| 10 | 2 | 1 | none | new convoy |
| 8 | 4 | 1 | 1 | joins: same moment |
| 5 | 1 | 7 | 1 | new convoy |
| 3 | 3 | 3 | 7 | joins |
| 0 | 1 | 12 | 7 | new convoy |
There are 3 convoys.
Input: target = 12, positions = [6, 0], speeds = [1, 2]
Output: 1The front bike needs 6 minutes. The bike behind needs 12 / 2 = 6 minutes as well, so it reaches the depot as the other arrives and joins it.
Input: target = 10, positions = [0, 3, 6], speeds = [1, 1, 1]
Output: 3With equal speeds, no bike ever catches the one ahead, so every bike is its own convoy.
0 ≤ positions.length = speeds.length ≤ 100,000 (bikes)1 ≤ target ≤ 1,000,0000 ≤ positions[i] < target, and all positions are different1 ≤ speeds[i] ≤ 1,000,000Comparing every bike with every bike ahead of it costs about n × n / 2, which is 5 × 10^9 at n = 100,000. Sorting by position costs n log n, and one pass after it costs n.
convoy_count · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.