First Circular tour to visit all the petrol bunks

Let there is a circle with n petrol pumps on the circle. Every petrol pump has pair of data. First value is amount of petrol pump has and second is distance from that petrol pump to the next petrol pump

Calculate the first point from where a vehicle will be able to complete a full circle. Vehicle should stop at each petrol pump and it has infinite capacity to store petrol.

Note : with 1 litre of petrol, vehicle can go 1 unit of distance.

Example

a) lnput: [{4, 6}, {6, 3}, {6, 7}]
    Output: start point is 1.
    Tour starts from index 2: (6-3) + (6-7) + (4-6) > 0, Tour starts from index 2

Algorithm

Time complexity: O(n)

Here we use a Queue to store the current tour. We create a struct to store the pair of data(petrol, distance)

a. We first enqueue first petrol pump to the Queue.

b. We keep enqueuing petrol pumps till we either complete the tour or current amount of petrol becomes negative.

c. If amount becomes negative, then we keep de-queueing petrol pumps till the current amount of petrol becomes positive or queue becomes empty.

d. Here we use the same array as queue, we maintain two index variables start and end that represent rear and front of queue.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
struct PetrolPumpData
{
  int petrol;
  int distance;
};
//function returns start point of tour
int StartPointOfTour(struct PetrolPumpData array[], int n)
{
    //Initialize start as first petrol bunk
    int start_point = 0;
    int end_point =  1;

    int curr_petrol = array[start_point].petrol - array[start_point].distance;
    while (end_point != start_point || curr_petrol < 0)
    {
        //If current petrol is negitive
        //remove first petrol pump and update start
        while (curr_petrol < 0 && start_point != end_point)
        {
            curr_petrol = curr_petrol - (array[start_point].petrol - array[start_point].distance);
            start_point = (start_point + 1)%n;
            //if zero is coming again as start point.
            //No solution
            //loop starting again
            if (start_point == 0)
               return -1;
        }
        //update current_petrol and end point
        //adding next petrol pump to Queue
        curr_petrol = curr_petrol + array[end_point].petrol - array[end_point].distance;
        end_point = (end_point + 1)%n;
    }
    //final start point
    return start_point;
}
 
//Main function
int main()
{
    struct PetrolPumpData input_array[] = {};
    int size = sizeof(input_array)/sizeof(input_array[0]);
    int result = StartPointOfTour(input_array,size);
    if(result == -1)
    {
        cout<<"No possible Tour"<<endl;
    }
    else
    {
        cout<<"Start point of tour is: "<<result<<endl;
    }
    return 0;
}
Try It


Next > < Prev
Scroll to Top