We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Data Structures
- Queues
- Truck Tour
- Discussions
Truck Tour
Truck Tour
Sort by
recency
|
353 Discussions
|
Please Login in order to post a comment
Easy python solution-
def truckTour(petrolpumps): n = len(petrolpumps) current_petrol = 0 total_petrol = 0 start_index = 0
Python
This is one of the easiest hard problems maybe.
A naive solution would be to start a tour from each gas station in turn, and check if the tour is feasible. A feasible tour is one where the fuel in the tank never goes negative while travelling. This is an O(n^2) algorithm.
However, it is easy to see that if a tour starting from S1 and passing through S2, S3, ..., Sk is infeasible, so is a tour from any Sj between S1 and Sk. So you don't need to check those, and the algorithm becomes O(n).
I am not sure queues were needed either -- but that's a cute opportunity to learn from the editorial :)
I'm suprised that the Python brute force approach passed all test cases
def truckTour(petrolpumps):