Minimice las recargas para llegar al final de la ruta

Ejemplos:

Entrada: objetivo = 1, M = 1, estaciones = { }
Salida: 0
Explicación:  Como es posible alcanzar el objetivo sin repostar.

Entrada: objetivo = 100, M = 1, estaciones = { {10, 100} }
Salida: -1
Explicación: No es posible llegar al objetivo (ni siquiera a la primera gasolinera).

Entrada: objetivo = 100, M = 10, estaciones = { {10, 60}, {20, 30}, {30, 30}, {60, 40}} Salida: 2 Explicación: Comenzando con 10
unidades de
combustible . 
Conduzca a la posición 10, gastando 10 unidades de combustible. 
Luego reposte desde 0 litros hasta 60 unidades de combustibles. 
Luego, conduzca desde la posición 10 a la posición 60 y reposte 40 litros de gasolina. 
Luego, simplemente conduzca y alcance el objetivo. 
Por lo tanto, hay 2 paradas de reabastecimiento de combustible en el camino.

Enfoque ingenuo: el enfoque básico es intentar cada combinación individual de 1 bomba de reabastecimiento de combustible, luego cada combinación individual de 2 paradas de reabastecimiento de combustible, etc. y encontrar la forma mínima.

Complejidad del tiempo:O(2 ^N ) Porque el número total de combinaciones posibles es ^N C ₁ + ^N C ₂ + ^N C ₃ + . . . + ^norte C _norte = 2 ^norte .
Espacio Auxiliar:O(1)

Enfoque eficiente: este problema se puede resolver utilizando un enfoque codicioso y un montón máximo basado en la siguiente idea:

• Como es necesario repostar un número mínimo de veces, no rellene el depósito hasta que sea posible llegar al siguiente surtidor de gasolina.
• Cuando ya no sea posible llegar al siguiente surtidor de gasolina, seleccione un surtidor de los cruzados hasta ahora y que no se utilice para repostar.
• Para minimizar las paradas, es óptimo elegir la bomba de gasolina con la máxima cantidad de combustible.

Para encontrar la bomba con el máximo de las ya visitadas en un tiempo óptimo, use max heap. Almacene las bombas de gasolina en el montón máximo mientras las cruza, y retírelas del montón cuando se usen.

Siga los pasos a continuación para resolver el problema:

• Ordena las estaciones en orden ascendente de su posición desde el inicio.
• Cree un montón máximo, digamos pq (implementado por la cola de prioridad).
• Atraviesa las estaciones desde i = 0 hasta N-1:
  • Compruebe si el coche puede llegar a la i-ésima estación sin repostar.
  • Si no puede llegar, busque la estación del montón máximo que tenga el combustible máximo y no se use para repostar entre las estaciones cruzadas hasta ahora e incremente el recuento de paradas de repostaje.
  • Inserte la i-ésima estación en el montón máximo
• Devuelve el conteo como la respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum
// refuel stops
int minRefuelStops(int T, int F,
                   vector<vector<int> >& S)
{
    int N = S.size(), ans = 0;
    sort(S.begin(), S.end());
 
    // Initializing max heap
    priority_queue<int> pq;
    for (int i = 0; i <= N; i++) {
        int dist = i == N ? T : S[i][0];
        while (F < dist) {
            if (!pq.size())
                return -1;
            F += pq.top(), ans++;
            pq.pop();
        }
        if (i < N)
            pq.push(S[i][1]);
    }
    return ans;
}
 
// Driver code
int main()
{
    int target = 100;
    int M = 10;
    vector<vector<int> > stations = {
        { 10, 60 }, { 20, 30 }, { 30, 30 }, { 60, 40 }
    };
 
    // Function call
    cout << minRefuelStops(target, M, stations);
    return 0;
}

// Java code to implement the approach
 
import java.util.*;
 
public class GFG {
    // Function to find the minimum number
    // of refueling stops
    static int minRefuelStops(int T, int F,
                              int[][] S)
    {
        int N = S.length, ans = 0;
 
        // Sort on the basis of
        // distance from the start
        Arrays.sort(S, new Comparator<int[]>() {
            public int compare(int[] a, int[] b)
            {
                return Integer.compare(a[0], b[0]);
            }
        });
        PriorityQueue<Integer> pq
            = new PriorityQueue<>((a, b)
                                      -> b - a);
        for (int i = 0; i <= N; i++) {
            int dist = i == N ? T : S[i][0];
            while (F < dist) {
                if (pq.size() == 0)
                    return -1;
                F += pq.poll();
                ans++;
            }
            if (i < N)
                pq.add(S[i][1]);
        }
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int target = 100, M = 10;
        int stations[][] = {
            { 10, 60 }, { 20, 30 }, { 30, 30 }, { 60, 40 }
        };
        System.out.println(
            minRefuelStops(target, M, stations));
    }
}
// this code is contributed by prophet1999

# python code for the above approach
import heapq
 
# Function to find minimum refuel stops
def minRefuelStops(T, F, S):
    N = len(S)
    ans = 0
    S.sort()
 
    # Initializing max heap
    pq = []
    for i in range(N+1):
        dist = T if i == N else S[i][0]
        while F < dist:
            if len(pq)==0:
                return -1
            ans+=1
            F += -1*heapq.heappop(pq)
        if i < N:
            heapq.heappush(pq, -1*S[i][1])
    return ans
 
 
# Driver Code
target = 100
M = 10
stations = [[10, 60], [20, 30], [30, 30], [60, 40]]
print(minRefuelStops(target, M, stations))
 
# This code is contributed by ishankhandelwals.

2

Complejidad del tiempo:O(N * log N)
Espacio auxiliar: O(N)