Two sub problems here:
1. is it possible to complete the circular route, just check if total = totalGas - totalCost is greater than 0
2. find the starting point
if the previousTotalGas < previousTotalCost, all the previous station could not be the starting point, we have to jump to the next station. Since there is only one solution.
You might doubt if any previous stations can be the starting point, but it will break the unique solution assumtion
Look at this, there will be more than 1 solution
gas = [1,2,2,2,9]
cost = [10,1,1,1,1]
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/Greedy/Q134GasStation.playground/Contents.swift
No comments:
Post a Comment