Question
There are n cars traveling to a destination. Each car has a
position and speed. A car can’t pass another car ahead of it.
A car will catch up to another only if it reaches the same position at the same time or later. Once they meet, they become a single car fleet and travel together.
Return the total number of car fleets that will arrive at the destination.
Example
Input:
target = 10
position = [6, 8]
speed = [3, 2]
Output: 2
Explanation: Car at position 6 reaches the target before catching car at position 8. So both arrive separately.
My Notes
- Pair each car’s position and speed together.
- Sort the cars based on their starting position (closest to target last).
- For each car, calculate the time it takes to reach the destination.
-
Use a stack to track fleets (based on arrival times):
- Start from the car closest to the destination.
- If a car arrives later than the car ahead → it becomes a new fleet.
- If it arrives earlier or same time → it merges into the existing fleet.
- ⏱️ Time = (target - position) / speed
- 🧠 This logic is similar to how you merge overlapping intervals: Merge Intervals. Cars that catch up are like overlapping intervals — they "merge" into one group.
package main
import (
"fmt"
"sort"
)
type Stack struct {
items []float64
}
func (s *Stack) Push(item float64) {
s.items = append(s.items, item)
}
func (s *Stack) Top() float64 {
return s.items[len(s.items)-1]
}
func carFleet(target int, position []int, speed []int) int {
l := len(position)
mergedArray := make([][]int, l)
stack := Stack{}
for i := range position {
mergedArray[i] = []int{position[i], speed[i]}
}
sort.Slice(mergedArray, func(i, j int) bool {
return mergedArray[i][0] < mergedArray[j][0]
})
stack.Push(float64(target - mergedArray[l-1][0]) / float64(mergedArray[l-1][1]))
for i := l - 2; i >= 0; i-- {
time := float64(target - mergedArray[i][0]) / float64(mergedArray[i][1])
if time > stack.Top() {
stack.Push(time)
}
}
return len(stack.items)
}
func main() {
result := carFleet(10, []int{6, 8}, []int{3, 2})
fmt.Println(result)
}