2
\$\begingroup\$

I am studying algorithms and I had to solve this algorithm:

Consider the following problem. You have a car such that if you fill it up to full tank, you can travel with it up to 400 kilometers without refilling it. And you need to get from point A to point B, and the distance between them is 950 kilometers. Of course, you need to refuel on your way, and luckily, there are a few gas stations on your way from A to B. These are denoted by blue circles, and the numbers above them mean the distance from A to the corresponding gas station along the way from A to B. And you need to find the minimum number of refuels to get from A to B.

I came up to a very different solution that the teacher and I would like to know your thoughts:

import java.io.*;
import java.util.*;

public class MinRefill{

 static int getMinRefill(int[] numbers, int refillAt) {
    int lastRefill=0;
    int currentRefill=0;
    int numOfRefills=0;
    int endPoint= numbers.length;

    while(currentRefill<endPoint-1){

        if(numbers[currentRefill+1]-numbers[currentRefill]>refillAt){
            return 0;
        }

        if(lastRefill+refillAt<numbers[currentRefill+1]){
            lastRefill=numbers[currentRefill];
            numOfRefills++;
        }

        currentRefill++;
    }


    return numOfRefills;
}
public static void main(String[] args) {

    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int[] numbers = new int[n];

    for (int i = 0; i < n; i++) {
        numbers[i] = in.nextInt();
    }

    System.out.println(getMinRefill(numbers,400));

}
}

Tested input:

0
0 200 375 550 750 950

0 = A and 950 = B

\$\endgroup\$
2
\$\begingroup\$

Your algorithm looks fine, and efficient. Strictly speaking, since the stations are sorted, you could use binary search to find the next station to refill, by looking for the insertion point of lastRefill + 400. This could speed things up if gas stations are extremely dense. But that's unrealistic anyway, so I think no need to bother, your simple implementation is fine.

The implementation is a bit hard to read because of the names. I recommend these renames:

  • numbers -> stations
  • refillAt -> capacity
  • numOfRefills -> refills

The writing style is also too compact and hard to read. It's recommended to put spaces around operators.

Lastly, the endpoint variable is redundant, stations.length is just as easy to understand.

With the renames and the formatting changed, the method becomes:

static int getMinRefill(int[] stations, int capacity) {
    int lastRefill = 0;
    int current = 0;
    int refills = 0;

    while (current < stations.length - 1) {

        if (stations[current + 1] - stations[current] > capacity) {
            return 0;
        }

        if (lastRefill + capacity < stations[current + 1]) {
            lastRefill = stations[current];
            refills++;
        }

        current++;
    }

    return refills;
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.