Car Fleet

TreeMap, Stack

Medium

N cars are going to the same destination along a one lane road. The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial positionposition[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored - they are assumed to have the same position.

A_car fleet_is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

How many car fleets will arrive at the destination?

Example 1:

Input: 
target = 
12
, position = 
[10,8,0,5,3]
, speed = 
[2,4,1,1,3]
Output: 
3
Explanation
:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Note:

1. 0 <= N <= 10 ^ 4

2. 0 < target <= 10 ^ 6

3. 0 < speed[i] <= 10 ^ 6

4. 0 <= position[i] < target

5. All initial positions are different.

Solution & Analysis

Sorting + Stack

新建一个class，记录每辆车Car的起始position和到达终点所需时间time；按照position排序。这样，在Stack中，维护一个按照time的单调递减栈，即每当位置在后的车B到达终点所需时间比位置在前的车A长时，说明A车会与B车相遇并组合成一个fleet，这时就不再需要A车，因此将A车从stack中pop()出来。注意这里要用while loop，因为当位置在后的车X到达时间较长时，位置在前的所有到达时间较短的车都会被X限制，从而成为一个fleet，也就是都要pop()出来了。最后stack的size就是fleet的数目。

参考思路1：

把车按照位置大小进行排序，计算出每个车在无阻拦的情况下到达终点的时间，如果后面的车到达终点所用的时间比前面车小，那么说明后车应该比前面的车先到。但是由于后车不能超过前车，所以这种情况下就会合并成一个车队，也就是说后车“消失了”。

像这种需要判断是否存在的题目一般都是用栈进行解决，对时间遍历，把哪些应该消失的车不进栈就行了。

作者：负雪明烛 来源：CSDN

原文：https://blog.csdn.net/fuxuemingzhu/article/details/81867361

参考思路2：

N辆车沿着一条车道驶向位于target英里之外的共同目的地。每辆车i以恒定的速度speed[i]（英里/小时），从初始位置 position[i]（英里）沿车道驶向目的地。 一辆车永远不会超过前面的另一辆车，但它可以追上去，并与前车以相同的速度紧接着行驶。此时，我们会忽略这两辆车之间的距离，也就是说，它们被假定处于相同的位置。车队是一些由行驶在相同位置、具有相同速度的车组成的非空集合。注意，一辆车也可以是一个车队。即便一辆车在目的地才赶上了一个车队，它们仍然会被视作是同一个车队。求会有多少车队到达目的地？

解法：先把车按照位置进行排序，然后计算出每个车在无阻拦的情况下到达终点的时间，如果后面的车到达终点所用的时间比前面车小，那么说明后车会比前面的车先到，由于后车不能超过前车，所以这种情况下就会合并成一个车队。用栈来存，对时间进行遍历，对于那些应该合并的车不进栈就行了，最后返回栈的长度。或者直接用一个变量存最近前车到达时间，用另一变量记录车队的数量，如果循环的时间大于记录的前车时间，则当前的车不会比之前的车先到达，为一个新车队，更新变量。

作者：轻风舞动 来源：cnblogs

原文：https://www.cnblogs.com/lightwindy/p/9795809.html

55 ms, faster than 39.83%

Complexity

• Time: O(n + nlogn)

• Space: O(n)

class Solution {
    class Car {
        int position;
        double time;

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

        @Override
        public String toString() {
            return this.position + ": " + this.time;
        }
    }
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        Car[] cars = new Car[n];
        for (int i = 0; i < position.length; i++) {
            cars[i] = new Car(position[i], 1.0 * (target - position[i]) / speed[i]);
        }

        Arrays.sort(cars, (c1, c2) -> Integer.compare(c1.position, c2.position));
        Deque<Car> stack = new ArrayDeque<>();

        for (Car c: cars) {
            while (!stack.isEmpty() && stack.peek().time <= c.time) {
                stack.pop();
            }
            stack.push(c);
        }
        return stack.size();
    }
}

TreeMap

By @lee215: https://leetcode.com/problems/car-fleet/discuss/139850/C%2B%2BJavaPython-Straight-Forward

Calculate time needed to arrive the target, sort by the start position. Loop on each car from the end to the beginning.currecorde the current biggest time (the slowest). If another car needs less or equal time thancur, it can catch up this car. Otherwise it will become the new slowest car, that is new lead of a car fleet.

Time Complexity: O(NlogN)

Space Complexity

O(N)

利用TreeMap，以position作为key，对key排序（位置的先后顺序），再从后往前，检查到达时间。

    public int carFleet(int target, int[] pos, int[] speed) {
        TreeMap<Integer, Double> m = new TreeMap<>();
        for (int i = 0; i < pos.length; ++i) m.put(-pos[i], (double)(target - pos[i]) / speed[i]);
        int res = 0; double cur = 0;
        for (double time : m.values()) {
            if (time > cur) {
                cur = time;
                res++;
            }
        }
        return res;
    }