Car Fleet

Patrick Leaton
Published: Nov. 3, 2021, 6:06 p.m.
Problem Description

There are n cars going to the same destination along a one-lane road. The destination is target miles away.

You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith 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 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.

 

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 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Example 2:

Input: target = 10, position = [3], speed = [3]
Output: 1

 

Constraints:

  • n == position.length == speed.length
  • 1 <= n <= 10^5
  • 0 < target <= 10^6
  • 0 <= position[i] < target
  • All the values of position are unique.
  • 0 < speed[i] <= 10^6

 

The description was taken from https://leetcode.com/problems/car-fleet/.

Problem Solution

#O(N(Log(N))) Time, O(N) Space
class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        heap = []
        last_fleet = None
        count = 0

        for i in range(len(position)):
            heapq.heappush(heap, (-position[i], speed[i]))
       
        while heap:
            position, speed = heapq.heappop(heap)
            completion = (target - (-position)) / speed
            if not last_fleet or completion > last_fleet:
                last_fleet = completion
                count += 1
               
        return count

Problem Explanation

We can solve this problem through a somewhat greedy algorithm.

A car will join a fleet if its completion time is faster than the completion time of a car ahead of it.

Knowing this, we can look at the completion time of the last car and see if the previous car will catch up to it by having a faster, lower completion time than it does.  If that is the case, then these two cars will be in the same car fleet.  If it is not, then they will be in two different car fleets.  We can repeat this process for each previous car. 

Let's start by initializing our heap, our previous fleet of cars to none, and our count to zero.

        heap = []
        last_fleet = None
        count = 0
 

Then, we will push each car into the heap, sorting it by its position.

Since Python uses min-heaps by default, we can create a make-shift max-heap by negating each value so that the largest positive value will become the smallest when negative.

The problem description says that the position values will be unique so we'll only need to negate the first element in the tuple because there won't ever be a tie that will require the second position to be considered in the sort.

        for i in range(len(position)):
            heapq.heappush(heap, (-position[i], speed[i]))

 

Now that we have each car in the heap sorted by their positions, we will begin looking at the car closest to the target and start working backward from there.

        while heap:

 

We'll pop a car's position and speed from the heap.

            position, speed = heapq.heappop(heap)

 

We will calculate the time it takes for it to reach the target by calculating the distance between the target and the position, then dividing that by the speed.

Also remember, we need to negate the position once more for it to become positive because we pushed its negative value into the heap.

            completion = (target - (-position)) / speed

 

Now, if this is the first car we popped off the heap so we don't yet have a previous fleet, or the current completion time is greater than the completion time of the previous fleet meaning it is slower and won't catch up to it, we will increment our count of car fleets by one and set the last fleet to the current completion time.

This will set a marker so we can see if the previous car will catch up to the current car in the next iteration, and this process will continue for each car.

            if not last_fleet or completion > last_fleet:
                last_fleet = completion
                count += 1

 

Once we have considered the completion time for each car, we will return the count of car fleets we have.

        return count