circuit

The Car Fueling Problem

Solving this algorithm problem in Python




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 algorithmthe 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โ€™.




Continue Learning