Car Fueling Problem (Greedy Algorithm), Nested while loop with O(n) complexity

user_12814260 0
Viewed 7141

Input

(1) the maximum distance that a car can travel with a full tank: L km;

(2) an integer array, [0, x1, x2, …, xn, xn+1], each integer represents the distance between a location and a source point A. The first integer is 0, which is the distance between A and A. The second distance x1, represents the distance between the first gas station and A. There are n gas stations between A and B (the destination). xn is the distance between the last gas station and A, and xn+1 is the distance between B and A.

(3) n, which is the number of gas stations.

Output

The minimum number of refills to get from A to B

Code

numRefills = 0
currentPosition = 0

while(currentPosition <= n){
    lastPosition = currentPosition

    while(currentPosition <= n  &&  x[currentPosition + 1] – x[lastPosition] <= L) {
    currentPosition++;
    }

    if (currentPosition == lastPosition) return IMPOSSIBLE; 
    if (currentPosition <= n) numRefills ++;
}

return numRefills

My doubts are:

  1. Why is the time-complexity of the above code is O(n)? shouldn't it be O(n^2) at least because of nested while loops?
  2. How to prove that "Refilling at farthest reachable gas" is a safe move?
  3. Are there any alternatives to writing the same code but using for loop?

(In short, I understood the logic but I am not able to compute it)

Any resources/help/hint/guidance is greatly appreciated!

greedy while-loop algorithm
3 Answers

Doubt 1:

Time complexity is calculated according to number of operation executed. Its not matter how many nested loop in there...

Your first while loop executed until currentPosition <= n and nested while loop executed until currentPosition <= n && x[currentPosition + 1] – x[lastPosition] <= L.. In this loop you increases currentPostion. So there is no possibility your total operation exceed n times.

Example:

array[0, 10, 20, 30] and L = 50..

For this case your first while loop true for 1st step.. You nested loop true for 4 steps. Then at 2nd step your first while loop false... So there executed N step...

Thats why your code complexiy : O ( N )...

Doubt 2:

To minimize refill , you need to go far as you can with current fuel.If you cross k station with current fuel then there is no need to fill tank at 1 to k-1 stations..At every station u need to check, is it possible to go next station with current fuel. If you can go from current station to next station with current fuel, then refill tank at current station is redundant.

Doubt 3:

There is many ways to solve a problem... Here is another one:

numRefills = 0
currentPosition = 0
currentFuel = L
while(currentPosition <= n){
   if (currentFuel <= x[currentPosition+1] - x[currentPosition]) {
      currentFuel = L;
      numRefills++;
   }
   currentFuel -= (x[currentPosition+1] - x[currentPostion]);
   if ( currentFuel < 0 ) 
      return Impossible;
   currentPosition++;
}

return numRefills
user_68312570 
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[k];
    for(int i=0;i<k;i++)
    {
        cin>>arr[i];
    }

    int diff=arr[0],refills=0,fuelCnt=3,flag=1;

    for(int i=0;i<k;i++)
    {
        if(i!=0)
        {
            diff=arr[i]-arr[i-1];
        }



        if(fuelCnt < diff)
        {
            fuelCnt=3;
            refills++;
        }
        fuelCnt-=diff;
        cout<<"fuelCnt is "<<fuelCnt<<"\n";
        if(fuelCnt <0)
        {
            flag=0;
            break;

        }
    }

    //Check if there is enough fuel to reach last stop
    diff=n-arr[k-1];
    fuelCnt-=diff;
    if(fuelCnt <0)
    {
        flag=0;
    }
    if(fuelCnt < diff)
    {
        refills++;
    }

    if(flag!=1)
    {
        cout<<"Imposible"<<"\n";
    }
    else
    {
        cout<<refills<<"\n";
    }

}

check whether code is correct ???
user_150848110

Coursera accept this solution in C++

#include <iostream>
#include <vector>
using namespace std;

int compute_min_refills(int dist, int tank, vector<int> &stops){
    stops.push_back(dist);
    int lastStop = 0;
    int numberStop = 0;
    int x = 0;

    for (int i = 0; i < stops.size() - 1; i++)
    {

        if (stops[i] - lastStop <= tank)
        {
            x = stops[i];
            if (stops[i + 1] - lastStop > tank)
            {
                numberStop++;
                lastStop = x;
            }
        }
        if (tank < stops[i] - lastStop)
        {
            //cout << "uzak" << endl;
            return -1;
        }

        //cout << "x :: " << x << "  last stop ::  " << lastStop << " number stop :: " << numberStop << endl;
    }
    if (dist > lastStop + tank)
    {
        return -1;
    }

    return numberStop;
}

int main()
{
    int d = 0;
    cin >> d;
    int m = 0;
    cin >> m;
    int n = 0;
    cin >> n;

    vector<int> stops(n);
    for (size_t i = 0; i < n; ++i)
        cin >> stops.at(i);

    cout << compute_min_refills(d, m, stops) << "\n";

    return 0;
}
user_150723150
Related