871. Minimum Number of Refueling Stops

A car travels from a starting position to a destination which is target miles east of the starting position.

There are gas stations along the way. The gas stations are represented as an array stations where stations[i] = [positioni, fueli] indicates that the ith gas station is positioni miles east of the starting position and has fueli liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses one liter of gas per one mile that it drives. When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

Return the minimum number of refueling stops the car must make in order to reach its destination. If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

大意:一哩耗一格油，初始有startFuel格油，要去target哩遠的地方，路上的加油站以[距離起點距離, 能加多少油]的二維數組形式儲存，試問最少加多少油可以抵達終點
因為有多少油等於可以跑多遠，所以直接把當前油量當作跑幾哩的計量就行，不需要跑了幾哩扣掉多少油，最終持有油量>=終點，即能抵達，否則返回-1。

解題思路：使用貪心算法，在能抵達的範圍內去能加最多的加油站加油，不考慮來回折返的情況
先把加油站依照儲存油量降序排序，就可以遍歷尋找能抵達的加油站進行加油，加完油就從數組中去除

var minRefuelStops = function(target, startFuel, stations) {
    let now = startFuel, count = 0;
    // 加油站依照儲存油量降序排序
    stations.sort(function(a, b){return b[1] - a[1]})
    while (now < target) {
        let fuel = 0; // 紀錄是否有可以抵達的加油站
        for (let i = 0; i < stations.length; i++) {
            if (stations[i][0] <= now) {
                // can reach station
                now += stations[i][1];
                stations.splice(i, 1); // remove the station
                count++;
                fuel = 1;
                break;
            }
        }
        if (fuel == 0) { // 所有加油站都抵達不了
            break;
        }

    }
    return now >= target ? count : -1;
};

結果