Find the first circular tour that visits all petrol pumps

Suppose there is a circle. There are n petrol pumps on that circle. You are given two sets of data.

1. The amount of petrol that every petrol pump has.
2. Distance from that petrol pump to the next petrol pump.

For example,
Let there be 4 petrol pumps with amount of petrol and distance to next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}.

Solution:

• We’ll pick any petrol pumps as starting point,
• Now there could be two possible than
• Either, we have enough petrol to reach next petrol pumps, in that case
  • We’ll move to next petrol pump
• Or, we haven’t enough petrol to reach next petrol pumps, in that case
  • We’ll back to one step back from starting point.

Algorithm:

• Start from 0th petrol pump
  • Set startIndex = 0, endIndex = startIndex + 1, availablePetrol = P0.petrol and distance = P0.distance
• Iterate till startIndex != endIndex
  • Iterate till startIndex != endIndex and availablePetrol < distance
    • Move one step back from starting point i.e. startIndex = (startIndex - 1 ) % totalPetrolPump
    • Update availablePetrol i.e. availablePetrol += P[startIndex].petrol
    • Update distance i.e. distance += P[startIndex].distance
  • Move one step next i.e. endIndex = (endIndex + 1) % totalPetrolPump
  • Update availablePetrol i.e. availablePetrol += P[startIndex].petrol
  • Update distance i.e. distance += P[startIndex].distance
• If our availablePetrol is less than distance then,
  • throw “Not possible” exception
• Return startIndex

Latest Source Code:
Github: PetrolPumpsCircularTour.java

Output:

Starting Point : C