Car Fleet - aloalgo
aloalgo logoaloalgo
Beta
Problems
Login

Car Fleet

Medium

You are given the positions and speeds of a set of cars on a one-lane road, where each car is represented by a pair of integers [position, speed]. You are also given an integer target which represents the destination.

Your task is to determine how many distinct car fleets will arrive at the target destination. A car fleet is defined as a group of cars that travel together at the same speed. The rules for fleet formation and behavior are as follows: If a faster car catches up to a slower car that is ahead of it, they will form a fleet. Upon forming a fleet, they will continue traveling together at the speed of the slower car. A crucial condition for forming a fleet is that the faster car must be behind the slower car and must reach the target at the same time as, or earlier than, the slower car. This implies that if the faster car would naturally arrive earlier, it will catch up and then reduce its speed to match the slower car. Once a fleet has formed, it effectively becomes a single unit and cannot be overtaken by any car behind it that is now part of its fleet.

Example 1

Inputs
target = 12
cars = [
  [10, 2],
  [8, 4],
  [0, 1],
  [3, 3],
  [5, 5]
]
Output
4
Explanation:

Let's calculate the time each car takes to reach the target (12):

  • Car at [10,2]: time = (12-10)/2 = 1.0
  • Car at [8,4]: time = (12-8)/4 = 1.0
  • Car at [0,1]: time = (12-0)/1 = 12.0
  • Car at [3,3]: time = (12-3)/3 = 3.0
  • Car at [5,5]: time = (12-5)/5 = 1.4

Sorted by position (and their times): [[0, 12.0], [3, 3.0], [5, 1.4], [8, 1.0], [10, 1.0]]

Processing from right to left (closest to target):

  1. Car [10, 1.0]: fleets = 1, max_time = 1.0 (forms a new fleet)
  2. Car [8, 1.0]: 1.0 <= max_time (1.0). This car catches up and joins the fleet. fleets = 1, max_time = 1.0.
  3. Car [5, 1.4]: 1.4 > max_time (1.0). This car takes longer, so it forms a new fleet. fleets = 2, max_time = 1.4.
  4. Car [3, 3.0]: 3.0 > max_time (1.4). This car takes longer, so it forms a new fleet. fleets = 3, max_time = 3.0.
  5. Car [0, 12.0]: 12.0 > max_time (3.0). This car takes longer, so it forms a new fleet. fleets = 4, max_time = 12.0.

Wait, there's a mistake in my manual trace. Let's re-evaluate Example 1 explanation and result.

Corrected Explanation for Example 1: Let's calculate the time each car takes to reach the target (12):

  • Car A: [10,2] -> time = (12-10)/2 = 1.0
  • Car B: [8,4] -> time = (12-8)/4 = 1.0
  • Car C: [0,1] -> time = (12-0)/1 = 12.0
  • Car D: [3,3] -> time = (12-3)/3 = 3.0
  • Car E: [5,5] -> time = (12-5)/5 = 1.4

Organize cars by position with their arrival times: Car C: [0, 12.0] Car D: [3, 3.0] Car E: [5, 1.4] Car B: [8, 1.0] Car A: [10, 1.0]

Iterate from the car closest to the target (right to left):

  1. Consider Car A ([10, 1.0]): max_time_to_reach_target is initially 0.0. Since 1.0 > 0.0, Car A forms a new fleet. fleets = 1, max_time_to_reach_target = 1.0.
  2. Consider Car B ([8, 1.0]): 1.0 <= max_time_to_reach_target (1.0). Car B catches up to Car A and joins its fleet. fleets remains 1. max_time_to_reach_target remains 1.0.
  3. Consider Car E ([5, 1.4]): 1.4 > max_time_to_reach_target (1.0). Car E will arrive after the fleet formed by A and B, so it forms a new fleet. fleets = 2, max_time_to_reach_target = 1.4.
  4. Consider Car D ([3, 3.0]): 3.0 > max_time_to_reach_target (1.4). Car D will arrive after the fleet formed by E, so it forms a new fleet. fleets = 3, max_time_to_reach_target = 3.0.
  5. Consider Car C ([0, 12.0]): 12.0 > max_time_to_reach_target (3.0). Car C will arrive after the fleet formed by D, so it forms a new fleet. fleets = 4, max_time_to_reach_target = 12.0.

Thus, 4 fleets arrive at the destination.

Example 2

Inputs
target = 10
cars = [
  [3, 3]
]
Output
1
Explanation:

Only one car, it forms a single fleet.

Example 3

Inputs
target = 100
cars = [
  [0, 2],
  [2, 1],
  [4, 2]
]
Output
2
Explanation:

Let's calculate times:

  • Car [0,2]: (100-0)/2 = 50.0
  • Car [2,1]: (100-2)/1 = 98.0
  • Car [4,2]: (100-4)/2 = 48.0

Sorted by position: [[0, 50.0], [2, 98.0], [4, 48.0]]

Processing from right to left:

  1. Car [4, 48.0]: max_time_to_reach_target is 0.0. 48.0 > 0.0. Forms new fleet. fleets = 1, max_time_to_reach_target = 48.0.
  2. Car [2, 98.0]: 98.0 > max_time_to_reach_target (48.0). Forms new fleet. fleets = 2, max_time_to_reach_target = 98.0.
  3. Car [0, 50.0]: 50.0 <= max_time_to_reach_target (98.0). This car will catch up and join the fleet led by car [2, 98.0]. fleets remains 2, max_time_to_reach_target remains 98.0.

Thus, 2 fleets arrive.

Loading...
Case 1Case 2Case 3
Inputs
target = 12
cars = [
  [10, 2],
  [8, 4],
  [0, 1],
  [3, 3],
  [5, 5]
]
Output
4
🤖

Hello! I am your ✨ AI assistant. I can provide you hints, explanations, give feedback on your code, and more. Just ask me anything related to the problem you're working on!