Given a 2D array arr[][] with each row of the form { X, Y }, where Y and X represents the minimum cost required to initiate a process and the total cost spent to complete the process respectively. The task is to find the minimum cost required to complete all the process of the given array if processes can be completed in any order.
Examples:
Input: arr[][] = { { 1, 2 }, { 2, 4 }, { 4, 8 } }Â
Output: 8Â
Explanation:Â
Consider an initial cost of 8.Â
Initiate the process arr[2] and after finishing the process, remaining cost = 8 – 4 = 4Â
Initiate the process arr[1] and after finishing the process, remaining cost = 4 – 2 = 2Â
Initiate the process arr[0] and after finishing the process, remaining cost = 2 – 1 = 1Â
Therefore, the required output is 8.Input: arr[][] = { { 1, 7 }, { 2, 8 }, { 3, 9 }, { 4, 10 }, { 5, 11 }, { 6, 12 } }Â
Output: 27
Approach: The problem can be solved using Greedy technique. Follow the steps below to solve the problem:
- Sort the array in descending order of Y.
- Initialize a variable, say minCost, to store the minimum cost required to complete all the process.
- Initialize a variable, say minCostInit, to store the minimum cost to initiate a process.
- Traverse the array using variable i. For every ith iteration, check if minCostInit is less than arr[i][1] or not. If found to be true then increment the value of minCost by (arr[i][1] – minCostInit) and update minCostInit = arr[i][1].
- In every ith iteration also update the value of minCostInit -= arr[i][0].
- Finally, print the value of minCost.
Below is the implementation of the above approach.
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 processint 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 Codeint 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 approachimport 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 processdef 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 Codeif __name__ == "__main__":Â Â Â Â arr = [[1, 2], [2, 4], [4, 8]]Â
Â
    # Function Call    print(minimumCostReqToCompthePrcess(arr)) |
C#
// C# program for the above approachÂ
using System;Â
class GFG{Â
  static int compare(int[] a, int[] b)  {    return b[1] - a[1];  }     // Function to find minimum cost required  // to complete all the process  static int minimumCostReqToCompthePrcess(    int[][] arr)  {Â
    // Sort the array on descending order of Y    Array.Sort(arr, compare);Â
    // 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 = { new int[] { 1, 2 },                   new int[] { 2, 4 },                   new int[] { 4, 8 } };Â
    // Function Call    Console.WriteLine(minimumCostReqToCompthePrcess(arr));  }}Â
// This code is contributed by phasing17 |
Javascript
<script>Â
// Javascript program to implement// the above approachÂ
// Function to find minimum cost required// to complete all the processfunction 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 Codevar arr = [ [ 1, 2 ],                               [ 2, 4 ],                               [ 4, 8 ] ];// Function Calldocument.write(minimumCostReqToCompthePrcess(arr));Â
// This code is contributed by rutvik_56.</script> |
Output:Â
8
Â
Time Complexity: O(N * log(N))Â
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
