853. Car Fleet

Link: https://leetcode.com/problems/car-fleet

Description: Given the position and speed of cars, calculate the number of car fleets that will arrive at the destination at the same time.

Solution:

Analogy:

Imagine a race where the finish line is at a certain distance (the target), and each racer (car) starts at different points and speeds. The key rule here is that a faster racer cannot overtake but can join up with a slower racer, and then they must move together at the slower speed. We want to find out how many groups (fleets) of racers will cross the finish line.

1. Simplified Explanation: Line Up the Racers by Start Line: First, we sort the cars based on how far they are from the start line (their position). This is like lining up the racers in the order they actually are on the track, so we know who can potentially catch up to whom.

2. Calculate Time to Finish Line: For each car, figure out how long it will take to reach the finish line (the target). This is like asking each racer, "Based on your speed and where you're starting, how long will it take you to reach the finish line?"

3. Find Groups Forming: Now, we look from the racer closest to the finish line towards those further away. We're checking to see if any racer will form a group with the racer in front because they are fast enough to catch up before the finish line.

   • If a racer will take longer to reach the finish line than the racer in front of them, they can't catch up. They will start a new group (fleet).
   • If they will reach the finish line at the same time or sooner, they join up with the racer in front into a single group because they've caught up.

4. Count the Groups: Each time we find a racer who starts a new group (because they can't catch up to the group in front), we have a new fleet. We count how many times this happens.

Key Points:

• Why Sort by Position: Sorting helps us consider racers in the correct order to see who can catch up to whom based on their starting positions.
• Time to Finish Line: This tells us whether a racer can catch up to another racer in front of them, forming a fleet, or if they'll end up starting a new fleet.
• Group Formation: A new group (fleet) forms when a racer cannot catch anyone in front of them by the finish line. If they can catch up, they're part of an existing group.
• Final Count: We're essentially counting how many "leaders" there are—racers who can't catch up to anyone in front of them and thus start a new group.

This approach cleverly simplifies a dynamic situation by focusing on the end result (the finish line) and working backward to see how interactions (catching up) between racers play out, allowing us to count the number of distinct groups or fleets that form by the race's end.

/**
 * @param {number} target
 * @param {number[]} position
 * @param {number[]} speed
 * @return {number}
 */
var carFleet = function (target, position, speed) {
  const carData = position.map((pos, index) => ({
    pos,
    time: (target - pos) / speed[index],
  }))

  // Sort cars based on their starting position
  carData.sort((a, b) => b.pos - a.pos)

  let fleets = 0
  let currentTimeToReach = 0 // Track the time to reach for the current lead car

  // Iterate over each car from closest to farthest from the destination
  for (const car of carData) {
    if (car.time > currentTimeToReach) {
      // If the car takes longer than the current fleet lead, it's a new fleet
      fleets += 1
      currentTimeToReach = car.time
    }
    // If car.time <= currentTimeToReach, the car joins the current fleet
  }

  return fleets
}