Dada una array 2D arr[][] con cada fila de la forma { X, Y } , donde Y y X representan el costo mínimo requerido para iniciar un proceso y el costo total gastado para completar el proceso respectivamente. La tarea es encontrar el costo mínimo requerido para completar todo el proceso de la array dada si los procesos se pueden completar en cualquier orden.
Ejemplos :
Entrada: arr[][] = { { 1, 2 }, { 2, 4 }, { 4, 8 } }
Salida: 8
Explicación:
Considere un costo inicial de 8.
Inicie el proceso arr[2] y luego de terminar el proceso, costo restante = 8 – 4 = 4
Inicia el proceso arr[1] y luego de terminar el proceso, costo restante = 4 – 2 = 2
Inicia el proceso arr[0] y luego de terminar el proceso, costo restante = 2 – 1 = 1
Por lo tanto, la salida requerida es 8.Entrada: arr[][] = { { 1, 7 }, { 2, 8 }, { 3, 9 }, { 4, 10 }, { 5, 11 }, { 6, 12 } }
Salida: 27
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Ordene la array en orden descendente de Y .
- Inicialice una variable, digamos minCost , para almacenar el costo mínimo requerido para completar todo el proceso.
- Inicialice una variable, digamos minCostInit , para almacenar el costo mínimo para iniciar un proceso.
- Recorre la array usando la variable i . Para cada i -ésima iteración, verifique si minCostInit es menor que arr[i][1] o no. Si se determina que es cierto, incremente el valor de minCost en (arr[i][1] – minCostInit) y actualice minCostInit = arr[i][1] .
- En cada i -ésima iteración también actualice el valor de minCostInit -= arr[i][0] .
- Finalmente, imprima el valor de minCost .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
bool func(pair<int, int> i1,
pair<int, int> i2)
{
return (i1.first - i1.second <
i2.first - i2.second);
}
// Function to find minimum cost required
// to complete all the process
int minimumCostReqToCompthePrcess(
vector<pair<int, int>> arr)
{
// Sort the array on descending order of Y
sort(arr.begin(), arr.end(), func);
// Stores length of array
int n = arr.size();
// Stores minimum cost required to
// complete all the process
int minCost = 0;
// Stores minimum cost to initiate
// any process
int minCostInit = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// If minCostInit is less than
// the cost to initiate the process
if (arr[i].second > minCostInit)
{
// Update minCost
minCost += (arr[i].second -
minCostInit);
// Update minCostInit
minCostInit = arr[i].second;
}
// Update minCostInit
minCostInit -= arr[i].first;
}
// Return minCost
return minCost;
}
// Driver Code
int main()
{
vector<pair<int, int>> arr = { { 1, 2 },
{ 2, 4 },
{ 4, 8 } };
// Function Call
cout << (minimumCostReqToCompthePrcess(arr));
}
// This code is contributed by grand_master
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find minimum cost required
// to complete all the process
static int minimumCostReqToCompthePrcess(
int[][] arr)
{
// Sort the array on descending order of Y
Arrays.sort(arr, (a, b)->b[1]-a[1]);
// Stores length of array
int n = arr.length;
// Stores minimum cost required to
// complete all the process
int minCost = 0;
// Stores minimum cost to initiate
// any process
int minCostInit = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// If minCostInit is less than
// the cost to initiate the process
if (arr[i][1] > minCostInit)
{
// Update minCost
minCost += (arr[i][1] -
minCostInit);
// Update minCostInit
minCostInit = arr[i][1];
}
// Update minCostInit
minCostInit -= arr[i][0];
}
// Return minCost
return minCost;
}
// Driver code
public static void main (String[] args)
{
int[][] arr = { { 1, 2 },
{ 2, 4 },
{ 4, 8 } };
// Function Call
System.out.println(minimumCostReqToCompthePrcess(arr));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach # Function to find minimum cost required # to complete all the process def minimumCostReqToCompthePrcess(arr): # Sort the array on descending order of Y arr.sort(key = lambda x: x[0] - x[1]) # Stores length of array n = len(arr) # Stores minimum cost required to # complete all the process minCost = 0 # Stores minimum cost to initiate # any process minCostInit = 0 # Traverse the array for i in range(n): # If minCostInit is less than # the cost to initiate the process if arr[i][1] > minCostInit: # Update minCost minCost += (arr[i][1] - minCostInit) # Update minCostInit minCostInit = arr[i][1] # Update minCostInit minCostInit -= arr[i][0] # Return minCost return minCost # Driver Code if __name__ == "__main__": arr = [[1, 2], [2, 4], [4, 8]] # Function Call print(minimumCostReqToCompthePrcess(arr))
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find minimum cost required
// to complete all the process
function minimumCostReqToCompthePrcess(arr)
{
// Sort the array on descending order of Y
arr=arr.map(row=>row).reverse()
// Stores length of array
var n = arr.length;
// Stores minimum cost required to
// complete all the process
var minCost = 0;
// Stores minimum cost to initiate
// any process
var minCostInit = 0;
// Traverse the array
for(var i = 0; i < n; i++)
{
// If minCostInit is less than
// the cost to initiate the process
if (arr[i][1] > minCostInit)
{
// Update minCost
minCost += (arr[i][1] -
minCostInit);
// Update minCostInit
minCostInit = arr[i][1];
}
// Update minCostInit
minCostInit -= arr[i][0];
}
// Return minCost
return minCost;
}
// Driver Code
var arr = [ [ 1, 2 ],
[ 2, 4 ],
[ 4, 8 ] ];
// Function Call
document.write(minimumCostReqToCompthePrcess(arr));
// This code is contributed by rutvik_56.
</script>
8
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA