Skip to content

853. Car Fleet

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct Car {
  int pos;
  double time;  // the time to reach the target
};

class Solution {
 public:
  int carFleet(int target, vector<int>& position, vector<int>& speed) {
    int ans = 0;
    vector<Car> cars(position.size());

    for (int i = 0; i < position.size(); ++i)
      cars[i] = {position[i], (double)(target - position[i]) / speed[i]};

    ranges::sort(cars,
                 [](const auto& a, const auto& b) { return a.pos > b.pos; });

    double maxTime = 0;  // the time of the slowest car to reach the target

    for (const Car& car : cars)
      // A car needs more time to reach the target, so it becomes the slowest.
      if (car.time > maxTime) {
        maxTime = car.time;
        ++ans;
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Car {
  public int pos;
  public double time;

  public Car(int pos, double time) {
    this.pos = pos;
    this.time = time;
  }
}

class Solution {
  public int carFleet(int target, int[] position, int[] speed) {
    int ans = 0;
    Car[] cars = new Car[position.length];

    for (int i = 0; i < position.length; ++i)
      cars[i] = new Car(position[i], (double) (target - position[i]) / speed[i]);

    Arrays.sort(cars, (a, b) -> b.pos - a.pos);

    double maxTime = 0; // the time of the slowest car to reach the target

    for (Car car : cars)
      // A car needs more time to reach the target, so it becomes the slowest.
      if (car.time > maxTime) {
        maxTime = car.time;
        ++ans;
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
    ans = 0
    times = [
        float(target - p) / s for p, s in sorted(zip(position, speed),
                                                 reverse=True)]
    maxTime = 0  # the time of the slowest car to reach the target

    for time in times:
      # A car needs more time to reach the target, so it becomes the slowest.
      if time > maxTime:
        maxTime = time
        ans += 1

    return ans