Car Fleet

Problem

There are n cars on a single-lane road heading toward a finish line at position target. Car i starts at position[i] (all starting positions are distinct) and drives at speed[i]. A car can never pass the car in front of it; when it catches up, it slows to the leader's speed and the two continue together as a single fleet. A fleet is one or more cars travelling bumper to bumper at the same speed. If a car catches another exactly at the finish line, they still count as one fleet.

Return the number of distinct fleets that cross the finish line.

• There are between 1 and 150,000 cars.
• target is a positive integer no larger than 2,000,000.
• Every starting position is a non-negative integer strictly less than target, and no two cars start at the same position.
• Every speed is a positive integer no larger than 2,000,000.

Examples

• target = 20, position = [14, 3, 9, 17, 0], speed = [3, 5, 4, 1, 2] → 3. The front car (17, speed 1) needs 3 time units; the cars at 14 (speed 3, needs 2) and 9 (speed 4, needs 2.75) would both arrive sooner, so they catch it and the three finish as one fleet. The car at 3 (speed 5) needs 3.4 and arrives alone, and the car at 0 (speed 2) needs 10 and never catches anyone.
• target = 50, position = [7], speed = [9] → 1. A single car is its own fleet.
• target = 30, position = [1, 4, 9], speed = [10, 6, 2] → 1. Each car behind is faster than the one ahead, so everyone eventually piles into the front car.

Hints

1. Instead of tracking positions over time, compute for each car how long it would take to reach the target if nothing were in its way.
2. A car behind another catches it before the finish exactly when its unobstructed arrival time is smaller or equal. Ordering by starting position makes "behind" and "ahead" precise.
3. Walk cars from closest-to-target to farthest, keeping a stack of fleet arrival times. A car whose time is at most the stack top merges into that fleet; otherwise it starts a new one.