Gas Station (Proof)
I. When total cost <= total gas, there is always a solution.
sum(x, y) = gas[x] - cost[x] + gas[x + 1] - cost[x + 1] + ... + gas[y] - cost[y]
We assume that [i, j] is the greatest range sum. Then, starting from i, we could travel the loop. Assume in contradiction that starting from i, there is a m stop the travel due to out of gas. . Thus, since total sum >= 0, sum[i, j] >= 0. Since total sum >= 0, we know A + B + C > 0. Since sum(A, B ) <= 0, then C >= 0. Then, sum(C, A) >= 0. Therefore, sum(C, A) will be the greatest range which is contradicted to the assumption.
II. When sum(i, j) < 0, start = i + 1
- Since there is always a solution, once we find a range sum < 0, we can let this range be the last range in the whole trip. Then, start = i + 1.
- Since the gain of previous stations are always >= 0, once we find a range sum[i, j] < 0, there is not a k satisfy that range sum[k, j] >= 0. Then, start = i + 1.
class Solution(object): def canCompleteCircuit(self, gas, cost): """ :type gas: List[int] :type cost: List[int] :rtype: int """ totalgas = 0 totalcost = 0 start = 0 balance = 0 for i in xrange(0, len(gas)): totalgas += gas[i] totalcost += cost[i] balance += gas[i] - cost[i] if balance < 0: start = i + 1 balance = 0 if totalcost <= totalgas: return start return -1
@ouqi fixed, thanks.
When total cost >= total gas, there is always a solution.
Are you sure this is the case? That means we don't have enough gas to make a full circuit.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.