Given a 2D array, arr[][] of size N, each row of which consists of the time required to complete 3 different types of tasks A, B, and C. The row elements arr[i][0], arr[i][1] and arr[i][2] are the time required to complete the ith task of type A, B and C respectively. The task is to find the minimum completion time to complete exactly K tasks from the array based on the following conditions:
- The same type of task will operate at the same time.
- Tasks of type B can be performed only when K tasks of type A have already been completed.
- Tasks of type C can be performed only when K tasks of type B have already been completed.
Examples:
Input: N = 3, K = 2, arr[][] = {{1, 2, 2}, {3, 4, 1}, {3, 1, 2}}
Output: 7
Explanation:
Minimum time required to complete K tasks of type A = min(max(arr[0][0], arr[2][0]), max(arr[0][0], arr[1][0]), max(arr[1][0], arr[2][0])) = min(max(1, 3), max(1, 3), max(3, 3)) 3
Minimum time required to complete K tasks of type B = max(arr[0][1], arr[2][1]) = 2
Therefore, select items 1 and 3 as the K tasks to be completed for minimum time.
Therefore, time to complete K tasks of type C = max(arr[0][2], arr[2][2]) = 2
Therefore, minimum time to complete K(= 2) of all types = 3 + 2 + 2 = 7Input: N = 3, K = 3, arr[][] = {{2, 4, 5}, {4, 5, 4}, {3, 4, 5}}
Output: 14
Approach: The problem can be solved using Recursion. The idea is to either select the ith row from the given array or not. The following are the recurrence relation.
MinTime(TA, TB, TC, K, i) = min(MinTime(max(arr[i][0], TA), max(arr[i][1], TB), max(arr[i][2], TC), K-1, i-1), MinTime(TA, TB, TC, K, i-1))
MinTime(TA, TB, TC, K, i) Stores the minimum time to complete K tasks.
i stores the position of the ith row of the given array elements.Base Case: if K == 0:
return TA + TB + TC
if i <= 0:
return Infinite
Follow the steps below to solve the problem:
- Initialize a variable, say X and Y while traversing each row recursively using the above recurrence relation.
- X stores the minimum completion time by selecting the ith row of the given array.
- Y stores the minimum completion time by not selecting the ith row of the given array.
- Find the value of X and Y using the above-mentioned recurrence relation.
- Finally, return the value of min(X, Y) for every row.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach#include<bits/stdc++.h>using namespace std;#define N 3// Function to get the minimum// completion time to select // exactly K itemsint MinTime(int arr[][N],int i, int Ta, int Tb, int Tc, int K){ // Base case if(K == 0) { return Ta + Tb + Tc; } if(i == 0) return INT_MAX; // Select the ith item int X = MinTime(arr, i - 1, max(Ta, arr[i - 1][0]), max(Tb, arr[i - 1][1]), max(Tc, arr[i - 1][2]), K -1); // Do not select the ith item int Y = MinTime(arr, i - 1, Ta, Tb, Tc, K); return min(X, Y);}// Driver Codeint main(){ int K = 2; int n = 3; int arr[N][N] = {{1, 2, 2} , {3, 4, 1} , {3, 1, 2} }; cout<<MinTime(arr, N, 0, 0, 0, K); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{// Function to get the minimum// completion time to select// exactly K itemspublic static int MinTime(int arr[][], int i, int Ta, int Tb, int Tc, int K){ // Base case if (K == 0) { return Ta + Tb + Tc; } if (i == 0) return Integer.MAX_VALUE; // Select the ith item int X = MinTime(arr, i - 1, Math.max(Ta, arr[i - 1][0]), Math.max(Tb, arr[i - 1][1]), Math.max(Tc, arr[i - 1][2]), K - 1); // Do not select the ith item int Y = MinTime(arr, i - 1, Ta, Tb, Tc, K); return Math.min(X, Y);}// Driver Codepublic static void main(String args[]){ int K = 2; int n = 3; int arr[][] = { { 1, 2, 2 }, { 3, 4, 1 }, { 3, 1, 2 } }; System.out.println(MinTime(arr, n, 0, 0, 0, K));}}// This code is contributed by hemanth gadarla |
Python3
# Python3 program to implement# the above approachN = 3# Function to get the minimum# completion time to select# exactly K itemsdef MinTime(arr, i, Ta, Tb, Tc, K): # Base case if (K == 0): return Ta + Tb + Tc if (i == 0): return 10**9 # Select the ith item X = MinTime(arr, i - 1, max(Ta, arr[i - 1][0]), max(Tb, arr[i - 1][1]), max(Tc, arr[i - 1][2]), K -1) # Do not select the ith item Y = MinTime(arr, i - 1, Ta, Tb, Tc, K) return min(X, Y)# Driver Codeif __name__ == '__main__': K = 2 n = 3 arr = [ [ 1, 2, 2 ], [ 3, 4, 1 ], [ 3, 1, 2 ] ] print(MinTime(arr, N, 0, 0, 0, K))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System;class GFG{// Function to get the minimum// completion time to select// exactly K itemspublic static int MinTime(int [,]arr, int i, int Ta, int Tb, int Tc, int K){ // Base case if (K == 0) { return Ta + Tb + Tc; } if (i == 0) return int.MaxValue; // Select the ith item int X = MinTime(arr, i - 1, Math.Max(Ta, arr[i - 1, 0]), Math.Max(Tb, arr[i - 1, 1]), Math.Max(Tc, arr[i - 1, 2]), K - 1); // Do not select the ith item int Y = MinTime(arr, i - 1, Ta, Tb, Tc, K); return Math.Min(X, Y);}// Driver Codepublic static void Main(String []args){ int K = 2; int n = 3; int [,]arr = {{1, 2, 2}, {3, 4, 1}, {3, 1, 2}}; Console.WriteLine(MinTime(arr, n, 0, 0, 0, K));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program to implement // the above approach // Function to get the minimum// completion time to select// exactly K itemsfunction Mletime(arr, i, Ta, Tb, Tc, K){ // Base case if (K == 0) { return Ta + Tb + Tc; } if (i == 0) return Number.MAX_VALUE; // Select the ith item let X = Mletime(arr, i - 1, Math.max(Ta, arr[i - 1][0]), Math.max(Tb, arr[i - 1][1]), Math.max(Tc, arr[i - 1][2]), K - 1); // Do not select the ith item let Y = Mletime(arr, i - 1, Ta, Tb, Tc, K); return Math.min(X, Y);}// Driver codeK = 2;let n = 3;let arr = [ [ 1, 2, 2 ], [ 3, 4, 1 ], [ 3, 1, 2 ] ];document.write(Mletime(arr, n, 0, 0, 0, K));// This code is contributed by splevel62 </script> |
Output
7
Time Complexity: O(2N)
Auxiliary Space: O(N)
Approach 2 :-
C++
#include <iostream>#include <bits/stdc++.h>using namespace std;int MinTime(vector<vector<int>>& tasks, int k) { // if k == 0 then return 0 if (k == 0) { return 0; } vector<pair<int, pair<int, int>>> arr; // make a pair of pair DS for (auto t : tasks) { arr.push_back({t[0], {t[1], t[2]}}); } // sort the pairs sort(arr.begin(), arr.end()); // initialize the ans as INT_MAX/2 int ans = INT_MAX / 2; for (int i = k - 1; i < arr.size(); i++) { vector<pair<int, int>> pr; // push the pairs into the pr vector for (int j = 0; j <= i; j++) { pr.push_back(arr[j].second); } // sort the pairs sort(pr.begin(), pr.end()); // priority queue priority_queue<int> q; for (int j = 0; j < pr.size(); j++) { q.push(pr[j].second); if (q.size() > k) { q.pop(); } if (q.size() == k) { ans = min(ans, arr[i].first + q.top() + pr[j].first); } } } return ans;}// Driver Codeint main() { int K = 2; int n = 3; vector<vector<int>> arr = {{1, 2, 2} , {3, 4, 1} , {3, 1, 2} }; cout<<MinTime(arr,K)<<endl; //This code is given by Akshay Verma return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{ static int MinTime(int[][] tasks, int k) { // if k == 0 then return 0 if (k == 0) { return 0; } ArrayList<int[]> arr = new ArrayList<>(); // make a pair of pair DS for (int[] t : tasks) { arr.add(new int[]{t[0], t[1], t[2]}); } // sort the pairs Collections.sort(arr, (a, b)->a[0] - b[0]); // initialize the ans as INT_MAX/2 int ans =Integer.MAX_VALUE / 2; for (int i = k - 1; i < arr.size(); i++) { ArrayList<int[]> pr = new ArrayList<>(); // push the pairs into the pr vector for (int j = 0; j <= i; j++) { pr.add(new int[]{arr.get(j)[1],arr.get(j)[2]}); } // sort the pairs Collections.sort(pr, (a, b)->a[0] - b[0]); // priority queue PriorityQueue<Integer> q = new PriorityQueue<>(); for (int j = 0; j < pr.size(); j++) { q.add(pr.get(j)[1]); if (q.size() > k) { q.poll(); } if (q.size() == k) { ans = Math.min(ans, arr.get(i)[0] + q.peek() + pr.get(j)[0]); } } } return ans; } // Driver code public static void main (String[] args) { int K = 2; int n = 3; int arr[][] = { { 1, 2, 2 }, { 3, 4, 1 }, { 3, 1, 2 } }; System.out.println(MinTime(arr,K)); }}// This code is contributed by offbeat |
Python3
# Python program to implement # the above approach import sysdef MinTime(tasks,k): # if k == 0 then return 0 if (k == 0): return 0 arr = [] # make a pair of pair DS for t in tasks: arr.append([t[0], t[1], t[2]]) # sort the pairs arr.sort() # initialize the ans as INT_MAX/2 ans = sys.maxsize//2 for i in range(k - 1, len(arr)): pr = [] # push the pairs into the pr vector for j in range(i+1): pr.append([arr[j][1],arr[j][2]]) # sort the pairs pr.sort() # priority queue q = [] for j in range(len(pr)): q.append(pr[j][1]) if(len(q) > k): q.pop(0) if(len(q) == k): ans=min(ans, arr[i][0] + q[0] + pr[j][0]) return ans # Driver code K = 2n = 3arr = [[1, 2, 2], [ 3, 4, 1 ], [3, 1, 2 ]]print(MinTime(arr, K))# This code is contributed by unknown2108 |
C#
// C# program to implement // the above approachusing System;using System.Collections.Generic;class GFG { static int MinTime(int[,] tasks, int k) { // if k == 0 then return 0 if (k == 0) { return 0; } List<List<int>> arr = new List<List<int>>(); // make a pair of pair DS for(int i = 0; i < tasks.GetLength(0); i++) { arr.Add(new List<int>()); for(int j = 0; j < tasks.GetLength(1); j++) { arr[i].Add(tasks[i,j]); } } // initialize the ans as INT_MAX/2 int ans = Int32.MaxValue / 2; for (int i = k - 1; i < arr.Count; i++) { List<List<int>> pr = new List<List<int>>(); // push the pairs into the pr vector for (int j = 0; j <= i; j++) { pr.Add(new List<int>()); pr[j].Add(arr[j][1]); pr[j].Add(arr[j][2]); } // priority queue List<int> q = new List<int>(); for (int j = 0; j < pr.Count; j++) { q.Add(pr[j][1]); q.Sort(); q.Reverse(); if (q.Count > k) { q.RemoveAt(0); } if (q.Count == k) { ans = Math.Min(ans, arr[i][0] + q[0] + pr[j][0]) + 1; } } } return ans; } // Driver code static void Main() { int K = 2; int[,] arr = { { 1, 2, 2 }, { 3, 4, 1 }, { 3, 1, 2 } }; Console.Write(MinTime(arr,K)); }}// This code is contributed by decode2207. |
Javascript
<script>// Javascript program to implement // the above approachfunction MinTime(tasks,k){ // if k == 0 then return 0 if (k == 0) { return 0; } let arr = []; // make a pair of pair DS for (let t=0;t< tasks.length;t++) { arr.push([tasks[t][0], tasks[t][1], tasks[t][2]]); } // sort the pairs arr.sort(function(a,b){return a[0]-b[0];}); // initialize the ans as INT_MAX/2 let ans =Number.MAX_VALUE / 2; for (let i = k - 1; i < arr.length; i++) { let pr = []; // push the pairs into the pr vector for (let j = 0; j <= i; j++) { pr.push([arr[j][1],arr[j][2]]); } // sort the pairs pr.sort(function(a,b){return a[0]-b[0];}); // priority queue let q = []; for (let j = 0; j < pr.length; j++) { q.push(pr[j][1]); if (q.length > k) { q.shift(); } if (q.length == k) { ans = Math.min(ans, arr[i][0] + q[0] + pr[j][0]); } } } return ans;}// Driver codelet K = 2;let n = 3;let arr=[[ 1, 2, 2 ], [ 3, 4, 1 ], [ 3, 1, 2 ]];document.write(MinTime(arr,K));// This code is contributed by patel2127</script> |
Output
7
Time Complexity :- O(N2logN)
Space Complexity:- O(N)
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!
