Greedy Problem Expedition Using C++

Today, we’ll learn to solve the greedy problem expedition using C++. It is one of the most popular problems from SPOJ(Sphere Online Judge). This problem also goes by the name EXPEDI on various other coding platforms. This has already been asked about during many coding competitions. We’ll learn to solve this problem most efficiently. Let’s go through the problem statement. Tighten your seat belts because this one is a bit tricker than other greedy problems.

Also read: Friends Pairing Problem Using Dynamic Programming In C++

Problem Statement of Greedy Problem Expedition

You were out on an expedition with some cows in your truck in a jungle. The cows, unfortunately, managed to run over a rock a puncture the truck’s fuel tank. The problem is that the truck now leaks one unit of fuel per unit distance it travels. You must reach the nearest town to search for a mechanic. During the journey, you’ll find N number of gas stations. You know the locations of all the gas stations on the way to town. Assume that your fuel tank can store an infinite amount of fuel. Assume that at each station the maximum fuel available is 100 units. The jungle is not safe for cows. Initially, the truck is L units away from the town. Initially, the truck contains P units of fuel. Find out the minimum number of stops in which you’ll reach the town.

Input Format

The input will be of the form:

N
d1 f1
d2 f2
........
..
.
..
........
dn fn
L P

Where N represent the number of gas stations on the way. And the following N lines represent the location of each fuel station and their fueling capacities respectively.

For example,

Input:
4
4 4
5 2
11 5
15 10
25 10
 
Output: 2

Approach

Key To Solving This Problem

We have to minimize the total number of stops during the journey. So, our greedy choice will be to refuel at stations that have larger fuel capacities. This’ll ensure that after each refuel, our reach is maximum. As a result, we’ll reach the destination in the minimum number of stops.

Pseudocode

Below is the step-by-step process that we’ll follow to implement the algorithm.

Sort the fuel stations based on the fuel available at each station.
Keep a note of available fuel stations.
If there’s a shortage of fuel. Use the gas station with the maximum fuel capacity.
In case, there’s still a shortage of fuel. Use another station with the maximum fuel capacity.
We’ll use the priority queue data structure to develop this functionality.

Greedy Problem Expedition Using C++ Program

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
bool compare(pair<int, int> p1, pair<int, int> p2)
{
    return p1.first > p2.first;
}
 
int main()
{
    int n, x, t, d, f, D, F, prev = 0;
    cin >> t;
 
    while (t--)
    {
        int flag = 0;
        int ans = 0;
        vector<pair<int, int>> v;
        priority_queue<int> pq;
 
        cout << "Enter the number of gas stations" << endl;
        cin >> n;
 
        cout << "Enter the distance of each gas station from the town" << endl;
        for (int i = 0; i < n; i++)
        {
            cin >> d >> f;
            v.push_back(make_pair(d, f));
        }
 
        //logic :
 
        sort(v.begin(), v.end(), compare);
 
        cout << "Enter the distance of the truck from the town and the initial fuel in the truck" << endl;
        cin >> D >> F;
 
        //update the distance of the fuel station from the truck
 
        for (int i = 0; i < n; i++)
        {
            v[i].first = D - v[i].first;
        }
 
        //prev denotes the previous city which have visited
 
        prev = 0;
        x = 0; //x denotes the current city
 
        while (x < n)
        {
            //if we have enough fuel to go to next city
 
            if (F >= (v[x].first - prev))
            {
                F = F - (v[x].first - prev);
 
                //since we reached the next city or the next fueling stop so our pq will add that stop
 
                pq.push(v[x].second);
                prev = v[x].first;
            }
            else
            {
                if (pq.empty())
                {
                    //there's no way to reach the town and hence we will return -1
 
                    flag = -1;
                    break;
                }
 
                //otherwise we can refuel the truck with fueling stations with higher capacity
 
                F += pq.top();
 
                //remove that fuel station from pq
 
                pq.pop();
 
                ans += 1;
                continue;
            }
            x++;
        }
        //once you are out of the while loop means that you have actually travelled n stations and now what's left
        //is you hae to reach the town from the last station
 
        if (flag == -1)
        {
            cout << -1 << endl;
        }
 
        //otherwise
 
        D = D - v[n - 1].first;
 
        if (F >= D)
        {
            cout << ans << endl;
            continue;
        }
 
        //otherwise
 
        while (F < D)
        {
            if (pq.empty())
            {
                flag = -1;
                break;
            }
 
            F += pq.top();
            pq.pop();
            ans += 1;
        }
 
        if (flag == -1)
        {
            cout << -1 << endl;
            continue;
        }
 
        cout << ans << endl;
    }
 
    return 0;
}

Output

Conclusion

In this article, we learned to solve the greedy problem expedition using C++. We used the STL(Standard Template Library) sort function and priority queue data structure to make use of our greedy choice. In the end, we implemented a C++ program to demonstrate the working of our solution. That’s all for today, thanks for reading.