Minimum time to complete at least K tasks when everyone rest after each task
Given an array arr[] of size N representing the time taken by a person to complete a task. Also, an array restTime[] which denotes the amount of time one person takes to rest after finishing a task. Each person is independent of others i.e. they can work simultaneously on different task at the same time. Given an integer K, the task is to find at least how much time will be taken to complete all the K tasks by all the persons.
Examples:
Input: arr[] = {1, 2, 4}, restTime[] = {1, 2, 2}, K = 5
Output: 5
Explanation: At t = 1, tasks task done = [1, 0, 0], Total task = 1
At t = 2, No of tasks completed = [1, 1, 0],
Total task = 1 + 1 = 2. Because 1st person was taking rest
At t = 3, No of tasks completed = [2, 1, 0],
Total task = 2 + 1 = 3, Because 2nd person was taking rest
At t = 4, No of tasks completed = [2, 1, 1],
Total task = 2 + 1 + 1 = 4, Because 1st and 2nd person was taking rest
At t = 5, No of tasks completed = [3, 1, 1].
Total task = 3 + 1 + 1 = 5. Minimum time taken = 5.Input: arr[] = {1, 2, 4, 7, 8}, restTime[] = {4, 1, 2, 3, 1}, TotalTask = 2
Output: 2
Approach: The problem can be solved using Binary Search, based on the following observations:
The minimum time taken can be 1 and maximum time required can be very large. If in time x all the K tasks can be completed, then it is also possible that they can be completed in less than x time. Use this concept to apply binary search on the time required.
Follow the below steps to implement the above approach:
- Create a variable st = 1, represent the starting point of the time range and end = INT_MAX, the ending point.
- Use binary search in the range from st to end:
- Calculate mid = st + (end – st)/2
- Check if K tasks can be completed in mid amount of time:
- If it can be completed then set end = mid-1.
- Else set st = mid+1.
- Return st at the end as this will be the minimum time required.
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if it is possible // to complete atleast totaltask using // current mid total time bool timePossible( int mid, int totalTask, vector< int >& timeArr, vector< int >& restTime) { // Variable to store total task int curTask = 0; // Loop to check if it is possible // to complete totalTask in mid time for ( int i = 0; i < timeArr.size(); i++) { int totalTime = timeArr[i] + restTime[i]; curTask += mid / totalTime; if (mid % totalTime >= timeArr[i]) curTask++; // Possible condition if (curTask >= totalTask) { return true ; } } // If possible print true if (curTask >= totalTask) { return true ; } // Else return false return false ; } // Function to find minimum time taken int minimumTimeTaken(vector< int >& timeArr, vector< int >& restTime, int totalTask) { // The ranges of time int st = 1; int end = INT_MAX; // Variable to store minimum time int minimumtime = 0; while (st <= end) { int mid = st + (end - st) / 2; // If this mid value is possible // try to minimise it if (timePossible(mid, totalTask, timeArr, restTime)) end = mid - 1; else st = mid + 1; } // Print the minimum time as answer return st; } // Driver code int main() { vector< int > arr = { 1, 2, 4 }; vector< int > restTime = { 1, 2, 2 }; int K = 5; // Function call cout << minimumTimeTaken(arr, restTime, K); return 0; } |
Java
// Java code for the above approach import java.io.*; class GFG { // Function to check if it is possible // to complete atleast totaltask using // current mid total time public static boolean timePossible( int mid, int totalTask, int timeArr[], int restTime[]) { // Variable to store total task int curTask = 0 ; // Loop to check if it is possible // to complete totalTask in mid time for ( int i = 0 ; i < timeArr.length; i++) { int totalTime = timeArr[i] + restTime[i]; curTask += mid / totalTime; if (mid % totalTime >= timeArr[i]) curTask++; // Possible condition if (curTask >= totalTask) { return true ; } } // If possible print true if (curTask >= totalTask) { return true ; } // Else return false return false ; } // Function to find minimum time taken public static int minimumTimeTaken( int timeArr[], int restTime[], int totalTask) { // The ranges of time int st = 1 ; int end = Integer.MAX_VALUE; // Variable to store minimum time int minimumtime = 0 ; while (st <= end) { int mid = st + (end - st) / 2 ; // If this mid value is possible // try to minimise it if (timePossible(mid, totalTask, timeArr, restTime) != false ) end = mid - 1 ; else st = mid + 1 ; } // Print the minimum time as answer return st; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 4 }; int restTime[] = { 1 , 2 , 2 }; int K = 5 ; // Function call System.out.print( minimumTimeTaken(arr, restTime, K)); } } // This code is contributed by Rohit Pradhan |
Python3
# python3 code for the above approach INT_MAX = 2147483647 # Function to check if it is possible # to complete atleast totaltask using # current mid total time def timePossible(mid, totalTask, timeArr, restTime): # Variable to store total task curTask = 0 # Loop to check if it is possible # to complete totalTask in mid time for i in range ( 0 , len (timeArr)): totalTime = timeArr[i] + restTime[i] curTask + = mid / / totalTime if (mid % totalTime > = timeArr[i]): curTask + = 1 # Possible condition if (curTask > = totalTask): return True # If possible print true if (curTask > = totalTask): return True # Else return false return False # Function to find minimum time taken def minimumTimeTaken(timeArr, restTime, totalTask): # The ranges of time st = 1 end = INT_MAX # Variable to store minimum time minimumtime = 0 while (st < = end): mid = st + (end - st) / / 2 # If this mid value is possible # try to minimise it if (timePossible(mid, totalTask, timeArr, restTime)): end = mid - 1 else : st = mid + 1 # Print the minimum time as answer return st # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 4 ] restTime = [ 1 , 2 , 2 ] K = 5 # Function call print (minimumTimeTaken(arr, restTime, K)) # This code is contributed by rakeshsahni |
C#
// C# program for above approach using System; class GFG { // Function to check if it is possible // to complete atleast totaltask using // current mid total time public static bool timePossible( int mid, int totalTask, int [] timeArr, int [] restTime) { // Variable to store total task int curTask = 0; // Loop to check if it is possible // to complete totalTask in mid time for ( int i = 0; i < timeArr.Length; i++) { int totalTime = timeArr[i] + restTime[i]; curTask += mid / totalTime; if (mid % totalTime >= timeArr[i]) curTask++; // Possible condition if (curTask >= totalTask) { return true ; } } // If possible print true if (curTask >= totalTask) { return true ; } // Else return false return false ; } // Function to find minimum time taken public static int minimumTimeTaken( int [] timeArr, int [] restTime, int totalTask) { // The ranges of time int st = 1; int end = Int32.MaxValue; // Variable to store minimum time int minimumtime = 0; while (st <= end) { int mid = st + (end - st) / 2; // If this mid value is possible // try to minimise it if (timePossible(mid, totalTask, timeArr, restTime) != false ) end = mid - 1; else st = mid + 1; } // Print the minimum time as answer return st; } // Driver Code public static void Main() { int [] arr = { 1, 2, 4 }; int [] restTime = { 1, 2, 2 }; int K = 5; // Function call Console.Write( minimumTimeTaken(arr, restTime, K)); } } // This code is contributed by code_hunt. |
Javascript
<script> // JavaScript code for the above approach // Function to check if it is possible // to complete atleast totaltask using // current mid total time function timePossible(mid, totalTask, timeArr, restTime) { // Variable to store total task let curTask = 0; // Loop to check if it is possible // to complete totalTask in mid time for (let i = 0; i < timeArr.length; i++) { let totalTime = timeArr[i] + restTime[i]; curTask += Math.floor(mid / totalTime); if (mid % totalTime >= timeArr[i]) curTask++; // Possible condition if (curTask >= totalTask) { return true ; } } // If possible print true if (curTask >= totalTask) { return true ; } // Else return false return false ; } // Function to find minimum time taken function minimumTimeTaken(timeArr, restTime, totalTask) { // The ranges of time let st = 1; let end = Number.MAX_VALUE; // Variable to store minimum time let minimumtime = 0; while (st <= end) { let mid = st + Math.floor((end - st) / 2); // If this mid value is possible // try to minimise it if (timePossible(mid, totalTask, timeArr, restTime)) end = mid - 1; else st = mid + 1; } // Print the minimum time as answer return st; } // Driver code let arr = [ 1, 2, 4 ]; let restTime = [ 1, 2, 2 ]; let K = 5; // Function call document.write(minimumTimeTaken(arr, restTime, K)); // This code is contributed by shinjanpatra </script> |
5
Time Complexity: O(N*log N)
Auxiliary Space: O(1)