853. Car Fleet

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

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

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

位置當然要排序過才好做

T:O(nlogn)

S: O(n)

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

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

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
*/