# 853. Car Fleet

• Time: $O(n\log n)$
• 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; // time to reach the target }; class Solution { public: int carFleet(int target, vector& position, vector& speed) { int ans = 0; vector cars(position.size()); for (int i = 0; i < position.size(); ++i) cars[i] = {position[i], (double)(target - position[i]) / speed[i]}; sort(begin(cars), end(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 auto& car : cars) // a car needs more time to reach the target, so it becomes 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 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 slowest if time > maxTime: maxTime = time ans += 1 return ans
Back to top