task there are n gas stations along a circular route where the amount of gas at the ith station is gasquantitiesi you have a car with an unlimited gas tank and it costs costsi of gas to travel from the ith station to its next i 1th station you begin the journey with an empty tank at one of the gas stations given two integer arrays gasquantities and costs return the starting gas station s index if you can travel around the circuit once in the clockwise direction otherwise return 1 if there exists a solution it is guaranteed to be unique reference https leetcode comproblemsgasstationdescription implementation notes first check whether the total gas is enough to complete the journey if not return 1 however if there is enough gas it is guaranteed that there is a valid starting index to reach the end of the journey greedily calculate the net gain gasquantity cost at each station if the net gain ever goes below 0 while iterating through the stations start checking from the next station this function returns a tuple of gas stations args gasquantities amount of gas available at each station costs the cost of gas required to move from one station to the next returns a tuple of gas stations gasstations getgasstations1 2 3 4 5 3 4 5 1 2 lengasstations 5 gasstations0 gasstationgasquantity1 cost3 gasstations1 gasstationgasquantity5 cost2 this function returns the index from which to start the journey in order to reach the end args gasquantities list amount of gas available at each station cost list the cost of gas required to move from one station to the next returns start int start index needed to complete the journey examples cancompletejourneygetgasstations1 2 3 4 5 3 4 5 1 2 3 cancompletejourneygetgasstations2 3 4 3 4 3 1 this function returns a tuple of gas stations args gas_quantities amount of gas available at each station costs the cost of gas required to move from one station to the next returns a tuple of gas stations gas_stations get_gas_stations 1 2 3 4 5 3 4 5 1 2 len gas_stations 5 gas_stations 0 gasstation gas_quantity 1 cost 3 gas_stations 1 gasstation gas_quantity 5 cost 2 this function returns the index from which to start the journey in order to reach the end args gas_quantities list amount of gas available at each station cost list the cost of gas required to move from one station to the next returns start int start index needed to complete the journey examples can_complete_journey get_gas_stations 1 2 3 4 5 3 4 5 1 2 3 can_complete_journey get_gas_stations 2 3 4 3 4 3 1
from dataclasses import dataclass


@dataclass
class GasStation:
    gas_quantity: int
    cost: int


def get_gas_stations(
    gas_quantities: list[int], costs: list[int]
) -> tuple[GasStation, ...]:
    
    return tuple(
        GasStation(quantity, cost) for quantity, cost in zip(gas_quantities, costs)
    )


def can_complete_journey(gas_stations: tuple[GasStation, ...]) -> int:
    
    total_gas = sum(gas_station.gas_quantity for gas_station in gas_stations)
    total_cost = sum(gas_station.cost for gas_station in gas_stations)
    if total_gas < total_cost:
        return -1

    start = 0
    net = 0
    for i, gas_station in enumerate(gas_stations):
        net += gas_station.gas_quantity - gas_station.cost
        if net < 0:
            start = i + 1
            net = 0
    return start


if __name__ == "__main__":
    import doctest

    doctest.testmod()