greedy_methods.gas_station

Task: There are n gas stations along a circular route, where the amount of gas at the ith station is gas_quantities[i].

You have a car with an unlimited gas tank and it costs costs[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas_quantities 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.com/problems/gas-station/description

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 (gas_quantity - cost) at each station. If the net gain ever goes below 0 while iterating through the stations, start checking from the next station.

Classes

GasStation

Functions

can_complete_journey(→ int)	This function returns the index from which to start the journey
get_gas_stations(→ tuple[GasStation, Ellipsis])	This function returns a tuple of gas stations.

Module Contents

class greedy_methods.gas_station.GasStation

cost: int

gas_quantity: int

greedy_methods.gas_station.can_complete_journey(gas_stations: tuple[GasStation, Ellipsis]) → int

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

greedy_methods.gas_station.get_gas_stations(gas_quantities: list[int], costs: list[int]) → tuple[GasStation, Ellipsis]

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)