I started taking the Algorithm design class from Coursera. So into the third week they talk about Greedy algorithms and walks through a sample problem.
This is the Problem Statement that I could find which was close.
Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car’s gas tank, when full, holds enough gas to travel ‘d’ miles, and his map gives the distances between gas stations on his route. The professor wishes to make as few stops as possible along the way. The problem is to find an efficient method by which Professor Midas can determine at which gas stations he should stop, and prove that the strategy adopted yields an optimal solution.
The INPUT: an Array containing the Distance of each gas station from the Starting Point , and an integer that contains the maximum distance that the car can go with full tank of gas.
OUTPUT: The Minimum Number of Stops that the Car must make at each gas station to make a successful trip.
Here's the Code
/*
* Week 3 , Algorythm Design Course Coursera
*
* Design an algorythm that computes the minimum Number of Refills that a car must make to reach
* the destination .
*
* INPUT :
* An Integer Array giving the distance of the GasStations from the Starting point ,
* An Integer that gives the maximum distance that the car can travel on a full refill
*
* OUTPUT:
* The Minimum Number of refills , that the car must make.
*/
var getLeastRefills = function(stationDist, maxDistance) {
var curPos = 1;
var minRefill = 0;
var curDistance = maxDistance;
var numRefillStations = (stationDist.length - 1);
while (curPos <= (numRefillStations)) {
for (; stationDist[curPos] <= curDistance; curPos += 1);
if (curPos > numRefillStations) return minRefill;
curPos -= 1;
minRefill += 1;
curDistance = stationDist[curPos] + maxDistance;
}
if (stationDist[curPos] < curDistance)
minRefill += 1;
return minRefill;
};
// Test Cases
console.log(getLeastRefills([0, 200, 375, 550, 750, 950], 400));
