The Car Fueling Problem

Problem Introduction

You are going to travel to another city that is located 𝑑 miles away from your home city. Your car can travel.

At most 𝑚 miles on a full tank and you start with a full tank. Along your way, there are gas stations at

Distances stop1, stop2, . . . , stop𝑛 from your home city. What is the minimum number of refills needed?

Problem Description

Input Format. The first line contains an integer 𝑑. The second line contains an integer 𝑚. The third line

Specifies an integer 𝑛. Finally, the last line contains integers stop1, stop2, . . . , stop𝑛.

Output Format

Assuming that the distance between the cities is 𝑑 miles, a car can travel at most 𝑚 miles

On a full tank, and there are gas stations at distances stop1, stop2, . . . , stop𝑛 along the way, output the

Minimum number of refills needed. Assume that the car starts with a full tank. If it is not possible to

Reach the destination, output −1.

Constraints

1 ≤ 𝑑 ≤ 105. 1 ≤ 𝑚 ≤ 400. 1 ≤ 𝑛 ≤ 300. 0 < stop1 < stop2 < · · · < stop𝑛 < 𝑑.

Sample 1

Input:

950

400

4

200 375 550 750

Output:

2

The distance between the cities is 950, the car can travel at most 400 miles on a full tank. It suffices

to make two refills: at points 375 and 750. This is the minimum number of refills as with a single refill

One would only be able to travel at most 800 miles.

Sample 2

Input:

10

3

4

1 2 5 9

Output:

-1

One cannot reach the gas station at point 9 as the previous gas station is too far away.

Greedy Strategy

1. Make a greedy choice!

2. Reduce to a smaller problem

3. Iterate

A greedy choice is a safe move if there is an optimal solution consistent with the first move:

1. Refill at the closest gas station

2. Refill at the farthest reachable gas station

3. Go until the fuel finishes up!

Implementation

the algorithm

Here, n is the total number of stops, x is an array with distance d i.e. x [d], currentRefill, lastRefills are nothing but indexes. Also, numRefills is the minimum number of fills.

Code

This problem is been practiced on Coursera platform under the the course ‘Algorithms Toolbox’.