Problem Description

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

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

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.

If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.

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

Example 1:

  • Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
  • Output: 3
  • Explanation:
    • The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at target.
    • The car starting at 0 (speed 1) does not catch up to any other car, so it is a fleet by itself.
    • The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Example 2:

  • Input: target = 100, position = [0,2,4], speed = [4,2,1]
  • Output: 1
  • Explanation:
    • The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The car starting at 4 (speed 1) travels to 5.
    • Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

My Idea

First we merge position and speed in a list of tuples representing the cars. Then we sort this list in a descending order in respect to their starting position. We use a stack to keep track of the number of fleets. For each car we calculate how much time it will take it to reach the target. If the time is less than or equal to the top element of the stack this means that this car will catch up with the car representing the top element and thus form a fleet with it. In this case we don’t modify the stack. If the car takes more time to reach target that means that it won’t catch up with the cars ahead of it and thus will be in a fleet of its own.

My solution

# Time Complexity: O(nlog(n))
def carFleet(target: int, position: list[int], speed: list[int]) -> int:
        cars = list(zip(position,speed))
        cars.sort(reverse=True)
        print(cars)
        fleets=[0]
        for c in cars:
            time=(target-c[0])/c[1]
            print(time)
            if fleets[-1]>=time:
                continue
            fleets.append(time)

        return len(fleets)-1