Car Fleet - Leetcode Solution

The Car Fleet problem on Leetcode asks you to find out the number of groups of cars that will arrive at a destination at the same time. The cars move at different speeds, and there are no intersections or traffic lights. The only thing that can stop them is another car that is moving slower than they are. This means that if the faster car catches up to the slower one, it will need to slow down until the slower car moves away.

To solve the problem, you need to simulate the movements of the cars and check how many groups you have at the end. The first step is to sort the cars by their initial position. Then, you can calculate the time it will take for each car to reach the destination based on its speed and initial position.

Once you have the time it will take for each car to arrive, you can create groups of cars that will arrive at the destination at the same time. To do this, you need to keep track of the maximum time it takes for a car to arrive in each group. If a car has a shorter time than the maximum time for the group, it will join the group. Otherwise, it will be the leader of a new group.

This algorithm has a time complexity of O(nlogn) because of the sorting step. The final step, where you create the groups, has a linear time complexity of O(n). Here's the solution in Python:

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        n = len(position)
        cars = sorted(zip(position, speed))
        times = [float(target - p) / s for p, s in cars]
        groups = []
        for t in times:
            if not groups:
                groups.append([t])
            elif t <= groups[-1][0]:
                groups[-1].append(t)
            else:
                groups.append([t])
        return len(groups)

In this solution, we use the zip() function to create pairs of positions and speeds for each car, and then use sorted() to sort the pairs by position. We calculate the time it will take for each car to reach the destination using the formula (target - p) / s, where p is the initial position and s is the speed.

Finally, we create groups of cars based on their arrival times and return the number of groups.

1