Find the first circular tour that visits all petrol pumps | GeeksforGeeks

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 petrol pump will give.
2. Distance from that petrol pump to the next petrol pump.
Calculate the first point from where a truck will be able to complete the circle (The truck will stop at each petrol pump and it has infinite capacity). Expected time complexity is O(n).

We can use a Queue to store the current tour. We first enqueue first petrol pump to the queue, we keep enqueueing petrol pumps till we either complete the tour, or current amount of petrol becomes negative. If the amount becomes negative, then we keep dequeueing petrol pumps till the current amount becomes positive or queue becomes empty.

int printTour(struct petrolPump arr[], int n)

{

    // Consider first petrol pump as a starting point

    int start = 0;

    int end =  1;

    int curr_petrol = arr[start].petrol - arr[start].distance;

    /* Run a loop while all petrol pumps are not visited.

      And we have reached first petrol pump again with 0 or more petrol */

    while (end != start || curr_petrol < 0)

    {

        // If curremt amount of petrol in truck becomes less than 0, then

        // remove the starting petrol pump from tour

        while (curr_petrol < 0 && start != end)

        {

            // Remove starting petrol pump. Change start

            curr_petrol -= arr[start].petrol - arr[start].distance;

            start = (start + 1)%n;

            // If 0 is being considered as start again, then there is no

            // possible solution

            if (start == 0)

               return -1;

        }

        // Add a petrol pump to current tour

        curr_petrol += arr[end].petrol - arr[end].distance;

        end = (end + 1)%n;

    }

    // Return starting point

    return start;

}

If we consider the items between start and end as part of a circular queue, we can observe that every item is enqueued at most two times to the queue. The total number of operations is proportional to total number of enqueue operations. Therefore the time complexity is O(n).
Read full article from Find the first circular tour that visits all petrol pumps | GeeksforGeeks