LeetCode 853: Car Fleet (Sort by Position + Reverse Scan)
LeetCode 853SortingGreedyToday we solve LeetCode 853 - Car Fleet.
Source: https://leetcode.com/problems/car-fleet/
English
Problem Summary
Each car starts at a different position and drives toward target with constant speed. Faster cars cannot pass slower cars ahead, so they may merge into fleets. Return how many fleets reach the destination.
Key Insight
Sort cars by position ascending, then scan from right to left (closest to target first). For each car, compute arrival time. If its time is greater than the current fleet time, it starts a new fleet. Otherwise it joins the fleet ahead.
Algorithm
- Pair each car as (position, speed).
- Sort by position ascending.
- Reverse scan and compute time = (target - position) / speed.
- Maintain lastTime (fleet time ahead). If time > lastTime, fleet count++, update lastTime.
- Else this car merges into existing fleet.
Complexity Analysis
Time: O(n log n) from sorting.
Space: O(n) for pairs.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
int[][] cars = new int[n][2];
for (int i = 0; i < n; i++) {
cars[i][0] = position[i];
cars[i][1] = speed[i];
}
Arrays.sort(cars, Comparator.comparingInt(a -> a[0]));
int fleets = 0;
double lastTime = -1.0;
for (int i = n - 1; i >= 0; i--) {
double t = (double) (target - cars[i][0]) / cars[i][1];
if (t > lastTime) {
fleets++;
lastTime = t;
}
}
return fleets;
}
}package main
import "sort"
func carFleet(target int, position []int, speed []int) int {
n := len(position)
type car struct{ p, s int }
cars := make([]car, n)
for i := 0; i < n; i++ {
cars[i] = car{position[i], speed[i]}
}
sort.Slice(cars, func(i, j int) bool { return cars[i].p < cars[j].p })
fleets := 0
lastTime := -1.0
for i := n - 1; i >= 0; i-- {
t := float64(target-cars[i].p) / float64(cars[i].s)
if t > lastTime {
fleets++
lastTime = t
}
}
return fleets
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int carFleet(int target, vector<int>& position, vector<int>& speed) {
int n = position.size();
vector<pair<int,int>> cars;
cars.reserve(n);
for (int i = 0; i < n; i++) cars.push_back({position[i], speed[i]});
sort(cars.begin(), cars.end());
int fleets = 0;
double lastTime = -1.0;
for (int i = n - 1; i >= 0; i--) {
double t = (double)(target - cars[i].first) / cars[i].second;
if (t > lastTime) {
fleets++;
lastTime = t;
}
}
return fleets;
}
};class Solution:
def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
cars = sorted(zip(position, speed))
fleets = 0
last_time = -1.0
for p, s in reversed(cars):
t = (target - p) / s
if t > last_time:
fleets += 1
last_time = t
return fleetsfunction carFleet(target, position, speed) {
const cars = position.map((p, i) => [p, speed[i]]).sort((a, b) => a[0] - b[0]);
let fleets = 0;
let lastTime = -1;
for (let i = cars.length - 1; i >= 0; i--) {
const [p, s] = cars[i];
const t = (target - p) / s;
if (t > lastTime) {
fleets++;
lastTime = t;
}
}
return fleets;
}中文
题目概述
有多辆车在不同位置，以各自固定速度驶向 target。后车不能超过前车，所以可能在追上后并入同一个车队。求最终到达终点的车队数量。
核心思路
按位置从小到大排序，然后从右往左扫描（离终点最近的车先看）。计算每辆车到终点所需时间：如果当前时间大于前方车队时间，就形成新车队；否则并入前方车队。
算法步骤
- 组合为 (position, speed) 并按位置升序排序。
- 从右向左计算每辆车到终点时间 t。
- 维护前方车队到达时间 lastTime。
- 若 t > lastTime，车队数加一并更新 lastTime；否则并入已有车队。
复杂度分析
时间复杂度：O(n log n)（排序）。
空间复杂度：O(n)（存储车辆对）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
int[][] cars = new int[n][2];
for (int i = 0; i < n; i++) {
cars[i][0] = position[i];
cars[i][1] = speed[i];
}
Arrays.sort(cars, Comparator.comparingInt(a -> a[0]));
int fleets = 0;
double lastTime = -1.0;
for (int i = n - 1; i >= 0; i--) {
double t = (double) (target - cars[i][0]) / cars[i][1];
if (t > lastTime) {
fleets++;
lastTime = t;
}
}
return fleets;
}
}package main
import "sort"
func carFleet(target int, position []int, speed []int) int {
n := len(position)
type car struct{ p, s int }
cars := make([]car, n)
for i := 0; i < n; i++ {
cars[i] = car{position[i], speed[i]}
}
sort.Slice(cars, func(i, j int) bool { return cars[i].p < cars[j].p })
fleets := 0
lastTime := -1.0
for i := n - 1; i >= 0; i-- {
t := float64(target-cars[i].p) / float64(cars[i].s)
if t > lastTime {
fleets++
lastTime = t
}
}
return fleets
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int carFleet(int target, vector<int>& position, vector<int>& speed) {
int n = position.size();
vector<pair<int,int>> cars;
cars.reserve(n);
for (int i = 0; i < n; i++) cars.push_back({position[i], speed[i]});
sort(cars.begin(), cars.end());
int fleets = 0;
double lastTime = -1.0;
for (int i = n - 1; i >= 0; i--) {
double t = (double)(target - cars[i].first) / cars[i].second;
if (t > lastTime) {
fleets++;
lastTime = t;
}
}
return fleets;
}
};class Solution:
def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
cars = sorted(zip(position, speed))
fleets = 0
last_time = -1.0
for p, s in reversed(cars):
t = (target - p) / s
if t > last_time:
fleets += 1
last_time = t
return fleetsfunction carFleet(target, position, speed) {
const cars = position.map((p, i) => [p, speed[i]]).sort((a, b) => a[0] - b[0]);
let fleets = 0;
let lastTime = -1;
for (let i = cars.length - 1; i >= 0; i--) {
const [p, s] = cars[i];
const t = (target - p) / s;
if (t > lastTime) {
fleets++;
lastTime = t;
}
}
return fleets;
}
Comments