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;
    }
}