853. Car Fleet - Medium

前往題目

思路

1. 排序好以後，從最後面開始往前看，如果前車比後車快就會catch up，然後位置靠左也就是前車會放慢速度跟後車並行，這時兩車視為一體了
2. 繼續往前看，以此類推

Code

其實可以不用再弄個class的😂

class Solution {
    class Car{
        private int position;
        private int speed;

        public Car() {

        }

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

        public int getPosition() {
            return position;
        }

        public int getSpeed() {
            return speed;
        }
    }

    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        Car[] cars = new Car[n];
        // 把每部車的資料放進去
        for (int i = 0; i < n; ++i) {
            cars[i] = new Car(position[i], speed[i]);
        }

        // 根據位置排序，由小到大
        Arrays.sort(cars, Comparator.comparingInt(Car::getPosition));

        int res = 0; // 結果

        // 從後往前
        for (int i = n - 1; i >= 0; --i) {
            // 算出當前車輛到達終點的時間，乘1.0是為了int轉double
            final double T = (target - cars[i].getPosition()) * 1.0 / 
                            cars[i].getSpeed();

            int j = i - 1; // 前車

            // 如果前車追得上
            while (j >= 0 && ((target - cars[j].getPosition()) * 1.0 / 
                            cars[j].getSpeed()) <= T) {
                --j; //檢查再前一部車
            }
            ++res;
            i = j + 1; // 其實是指到新的車，因為下個循環i會再減一
        }
        return res;
    }
}

2025/04/18

下面的解法似乎更直觀

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        // position, speed
        int[][] pair = new int[position.length][2];

        for (int i = 0; i < n; ++i) {
            pair[i][0] = position[i];
            pair[i][1] = speed[i];
        }
        // Large to small
        Arrays.sort(pair, (a, b) -> Integer.compare(b[0], a[0]));

        int fleets = 1;
        double prevTime = 1.0 * (target - pair[0][0]) / pair[0][1];

        for (int i = 1; i < n; ++i) {
            double currTime = 1.0 * (target - pair[i][0]) / pair[i][1];
            
            // Current car will be late, couldn't catch up to the front car
            // Therefore form a new fleet
            if (currTime > prevTime) {
                ++fleets;
                prevTime = currTime;
            }
        }

        return fleets;
    }
}