431. Convoy Count
Delivery vans start at different spots on a one-lane road that ends at a depot at mile target. Van i starts at position[i] and drives at a constant speed[i] miles per hour, but it can never overtake the van in front of it: if it catches up, it slows down and trails that van at the same speed from then on.
A convoy is a group of vans that reach the depot together, including a van driving alone. Vans that catch up exactly at the depot also count as one convoy. Return how many convoys arrive at the depot. All starting positions are distinct, and every van starts strictly before the depot. There can be up to 100,000 vans.
Example 1
- Input:
- target = 31position = [4,21,9,17,0]speed = [3,2,4,5,8]
- Output:
- 3
- Explanation:
Free arrival times from the front are 5 h (position 21), 2.8 h (17), 5.5 h (9), 9 h (4) and 3.875 h (0). The vans at 17 and 0 are held up by the vans ahead of them, which gives the convoys {21, 17}, {9} and {4, 0}: 3 in total.
Example 2
- Input:
- target = 40, position = [5,15,25], speed = [6,3,1]
- Output:
- 1
- Explanation:
The front van needs 15 hours, while the other two would need about 8.3 and 5.8 hours, so both are held up behind it and everyone arrives together: 1 convoy.
Constraints
1 ≤ position.length == speed.length ≤ 105
0 ≤ position[i] < target ≤ 2 * 106
All position[i] are distinct.
1 ≤ speed[i] ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)