You are given two integer arrays position and speed, both of length n, where position[i] is the position of the i-th car and speed[i] is the speed of the i-th car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car's speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

Return the number of car fleets that will arrive at the destination.

Company Tags: Amazon

Core Concept: Array, Sorting, Stack

Solve on LeetCode

34:T54a, - The key insight is to think about the time it takes for each car to reach the destination if there were no other cars. - If a car behind has a shorter arrival time than a car in front of it, it will catch up and form a fleet. They will then travel at the speed of the front car. This means the time to arrival for this new fleet is determined by the *original* arrival time of the front car. - **Algorithm**: 1. Combine the position and speed for each car into pairs. 2. Sort these pairs based on their starting position in descending order (from closest to the target to farthest). 3. Iterate through the sorted cars. For each car, calculate its time to arrival: `(target - position) / speed`. 4. Use a stack to keep track of the arrival times of the fleets. 5. For each car's calculated arrival ti

Non-overlapping Intervals (#435)

View Hints

View Solution