Convoys to the Finish
MediumStack
Problem
Delivery vans drive along a one-lane road towards a depot at position target. Van i starts at positions[i] (all distinct, all before the depot) and drives at constant speed speeds[i]. Vans cannot overtake: a faster van that catches up with a slower one stays right behind it, and from then on they travel together as one convoy at the slower speed.
A van that catches up exactly at the depot also joins that convoy. Return how many convoys arrive at the depot.
Example 1
- Input:
- target = 20, positions = [0, 5, 12], speeds = [4, 1, 2]
- Output:
- 2
Alone, the vans would need 5, 15 and 4 hours. The van at 12 arrives first on its own. The van at 0 catches the slow van at 5, so they arrive together: 2 convoys.
Example 2
- Input:
- target = 10, positions = [3], speeds = [2]
- Output:
- 1
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ positions[i] < target ≤ 10^6
- 1 ≤ speeds[i] ≤ 10^6
- All positions are distinct
Hint
Show the first hint
Ignore interactions for a moment: when would each van arrive if the road were empty?
Walkthrough
How to approach it
01Clarify before coding
- Does catching up exactly at the depot count as merging? Yes.
- Can two vans start at the same position? No, positions are distinct.
- Is the input sorted by position? No, sort it.
02Brute force
Simulate time in small steps, moving vans and merging them when they touch.
Cost: Depends on time resolution and is fragile with fractional meeting times; event simulation is O(n²) in the worst case.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.