> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/sort/853.-car-fleet.md).

# 853. Car Fleet

## use sort, when there is a new slower one means a new fleet

由題目得知, 夠快的車, 就會跟現在有車隊變同一個, 

所以反過來說, 慢的車, 會自成一個車隊, 所以可以利用這點來做

位置當然要排序過才好做

T:O(nlogn)

S: O(n)

```java
class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        double[][] data = new double[n][2];
        for (int i = 0; i < n; i++) {
            data[i][0] = position[i];
            data[i][1] = (double)(target - position[i])/speed[i];
        }
        Arrays.sort(data, (a,b) -> Double.compare(a[0], b[0]));
        
        double currBiggestTime = 0;
        int fleet = 0;
        for (int i = n-1; i >= 0; i--) {
            if (data[i][1] > currBiggestTime) {
                currBiggestTime = data[i][1];
                fleet++;
            }
        }
        return fleet;
    }
}

/*
(destination - position)/speed = time to destination

1.
so if 2 cars time to destination, are == or 1 car is faster, 
they will run together(become same fleet, fleet doesnt change) to destination

2.
so if one car is slower(needs more time), it become another fleet(fleet++)

so 

cal time for each car position(from end)

end to start poistion, if end-1 car's T > end car's T, fleet++

*/j
```

## TreeMap

```java
class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        TreeMap<Integer, Double> map = new TreeMap<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            map.put(position[i], (double)(target - position[i])/speed[i]);
        }
        double currBiggestTime = 0;
        int fleets = 0;
        
        for (double currTime : map.values()) { // use time!
            if (currTime > currBiggestTime) {
                currBiggestTime = currTime;
                fleets++;
            }
        }
        return fleets;
    }
}
```

#### by class, and and sort desc

```java
class Solution {
    class Data {
        int position;
        double time;
        Data(int position, double time) {
            this.position = position;
            this.time = time;
        }
    }
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        List<Data> data = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            double time = (double)(target - position[i])/speed[i];
            data.add(new Data(position[i], time));
        }
        Collections.sort(data, (a, b) -> b.position - a.position); // 大 -> 小
        
        double biggestTime = 0;
        int fleets = 0;
        for (int i = 0; i < n; i++) {
            Data cur = data.get(i);
            if (cur.time > biggestTime) {
                fleets++;
                biggestTime = cur.time;
            }
        }
        return fleets;
    }
}

/*
T: O(nlogn)
S: O(n)

10
[0,4,2]
[2,1,3]

0 2 4 10
10/2 = 5
  8/3 = 2.6...
    6/1 = 6

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3

1  3 1 4 2 
0  3.5 8 10 12
12
  9/3 = 3
    12-5 = 7 
      12-8 =4/4 = 1
      (12-10)/2 = 1
*/
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/sort/853.-car-fleet.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.