Delivery trucks are driving along a single-lane road toward a depot at mile target. Truck i starts at mile position[i] and drives at a constant speed[i] miles per hour. Nobody can overtake: when a faster truck catches up with a slower one ahead of it, it slows down and they drive on together as one convoy at the slower speed. A convoy can catch up with another convoy and merge with it in the same way.
If a truck catches up with another exactly at the depot, they still count as one convoy. A truck on its own is a convoy of one.
Write count_convoys(target, position, speed) that returns how many convoys arrive at the depot.
count_convoys(20, [14, 2, 10, 0], [2, 6, 1, 1]) # 3
# The truck at 14 arrives alone after 3 hours. The truck at 2 would need 3 hours
# too, but it catches the slow truck at 10 on the way. The truck at 0 arrives last, alone.
count_convoys(10, [4], [3]) # 1
count_convoys(10, [0, 5], [5, 1]) # 1 (the fast truck catches up)
count_convoys(10, [0, 5], [1, 5]) # 2
count_convoys(12, [0, 6], [2, 1]) # 1 (they meet exactly at the depot)
Constraints: 1 <= n <= 10^5 where n = len(position) == len(speed); 1 <= target <= 10^6; the positions are distinct and 0 <= position[i] < target; 1 <= speed[i] <= 100.
Comparing every pair of trucks is O(n²). Aim for O(n log n).
Show hint
process trucks from the one closest to the depot backwards. Work out when each truck would arrive if the road were empty; a truck only starts a new convoy if it would arrive strictly later than the convoy directly ahead of it.