-
Notifications
You must be signed in to change notification settings - Fork 0
/
Gas_Station.cpp
31 lines (27 loc) · 937 Bytes
/
Gas_Station.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 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,
// otherwise return -1.
// Note:
// The solution is guaranteed to be unique.
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int tank = 0, total = 0;
int start = 0;
for (int i = 0; i < gas.size(); i++) {
tank += (gas[i] - cost[i]);
total += (gas[i] - cost[i]);
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
if (total >= 0)
return start;
return -1;
}
};