GasStation.cpp

//Copyright [2018] [Haibo Yan]
//
//Licensed under the Apache License, Version 2.0 (the "License");
//you may not use this file except in compliance with the License.
//You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
//Unless required by applicable law or agreed to in writing, software
//distributed under the License is distributed on an "AS IS" BASIS,
//WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//See the License for the specific language governing permissions and
//limitations under the License
//
// Created by Haibo Yan on 4/20/18.
//

#include "GasStation.h"


// see https://leetcode.com/problems/gas-station/
// There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
//
//You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station
// (i+1). You begin the journey with an empty tank at one of the gas stations.
//Return the starting gas station's index if you can travel around the circuit once in the clockwise direction,
// otherwise return -1.
//Note: If there exists a solution, it is guaranteed to be unique.
//
//Example 1:
//Input:
//gas  = [1,2,3,4,5]
//cost = [3,4,5,1,2]
//Output: 3
//Explanation:
//Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
//Travel to station 4. Your tank = 4 - 1 + 5 = 8
//Travel to station 0. Your tank = 8 - 2 + 1 = 7
//Travel to station 1. Your tank = 7 - 3 + 2 = 6
//Travel to station 2. Your tank = 6 - 4 + 3 = 5
//Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
//Therefore, return 3 as the starting index.
//
//Example 2:
//Input:
//gas  = [2,3,4]
//cost = [3,4,3]
//Output: -1
//Explanation:
//You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
//Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
//Travel to station 0. Your tank = 4 - 3 + 2 = 3
//Travel to station 1. Your tank = 3 - 3 + 3 = 3
//You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
//Therefore, you can't travel around the circuit once no matter where you start.
int GasStation::canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int sumRemain = 0;
    int total = 0;
    int start = 0;

    for (int i = 0; i < gas.size(); i++) {
        int remain = gas[i] - cost[i];

        if (sumRemain >= 0) {
            sumRemain += remain;
        } else {
            sumRemain = remain;
            start = i;
        }

        total += remain;
    }

    if (total >= 0) {
        return start;
    } else {
        return -1;
    }
}