Minimum time to pick all elements with a cooldown period
Given an array arr[] of size n, where each element in the array represents a value between 1 and n. Additionally, you are given another array time[], where time[i] (1 ≤ i ≤ n) represents the minimum time required before you can pick the ith element again after you have already picked it, the task is to determine the minimum amount of time required to pick all the elements of the arr[] array from left to right, subject to the following condition: once you have picked an element, you must wait for time[element] seconds before you can pick it again. You can move from one index i to another index i+1 in one second, and there is no additional time required to pick an element. Follow 1- based indexing, meaning the first element is at index 1.
Examples:
Input: n = 4, arr[] = {1, 2, 3, 3}, time[]= {1, 2, 3, 4}
Output: 5
Explanation:
- You start from index 1, and pick arr[1] i.e. 1 in no time.
- In 1 sec you move from index 1 to 2, and pick arr[2] i.e. 2, total time = 1.
- In next 1 sec you move from index 2 to 3, and pick arr[3] i.e. 3, total time = 2.
- In next 1 sec you move from index 3 to 4, and arr[4] is 3, which you have taken already at time 2, hence you need to wait for time[arr[i]] sec to again pick arr[i], time[arr[i]] = time[3] = 3, hence in 1 sec you moved from index 3 to 4, and waited for next 2 sec, and finally picked arr[4], total time = 5.
Input: n = 4, arr[] = {1, 2, 3, 4}, time[] = {1, 2, 3, 4}
Output: 3
Explanation: All the array elements are different hence, you do not have to wait for any arr[i] before picking it, hence the total time will be 3, which is the time required to traverse the array.
Approach: To solve the problem follow the below steps:
- Declare a HashMap<Integer, Integer> to keep a track of the element that already came along with its previous time.
- Declare a cache array to store the time of individual elements when they can be picked.
- Traverse through the array and if the element is not present in the map in the form of a key, we add the element and the previous time from cache array +1 in the map.
- Else if it is present, we calculate the waiting time, the element has to wait before its time is updated and we store that waited time in a variable and check with the time array, if it has achieved the stimulated time, we update it in the cache array.
- Return the value of cache[n-1].
Below is the code for the above approach:
C++
//C++ program to find total time #include <bits/stdc++.h> #include <iostream> using namespace std; int totalTime( int n, int arr[], int time []) { map< int , int > hm; vector< long long > cache(n); hm[arr[0]] = 0; cache[0] = 0; for ( int i = 1; i < n; i++) { if (hm.count(arr[i])) { long long currentTime = cache[i - 1] + 1; long long previousTime = cache[hm[arr[i]]]; long long waited = currentTime - previousTime; if (waited < time [arr[i] - 1]) { currentTime += time [arr[i] - 1] - waited; } cache[i] = currentTime; hm[arr[i]] = i; } else { hm[arr[i]] = i; cache[i] = cache[i - 1] + 1; } } return cache[n - 1]; } int main() { int n = 4; int arr[] = { 1, 2, 3, 3 }; int time [] = { 1, 2, 3, 4 }; cout << totalTime(n, arr, time ); return 0; } // This code is contributed by Raunak Singh |
Java
// Java program to find total time import java.io.*; import java.util.*; class GFG { public static long totalTime( int n, int arr[], int time[]) { HashMap<Integer, Integer> hm = new HashMap<>(); long cache[] = new long [n]; hm.put(arr[ 0 ], 0 ); cache[ 0 ] = 0 ; for ( int i = 1 ; i < n; i++) { if (hm.containsKey(arr[i])) { long currentTime = cache[i - 1 ] + 1 ; long previousTime = cache[hm.get(arr[i])]; long waited = currentTime - previousTime; if (waited < time[arr[i] - 1 ]) { currentTime += time[arr[i] - 1 ] - waited; } cache[i] = currentTime; hm.put(arr[i], i); } else { hm.put(arr[i], i); cache[i] = cache[i - 1 ] + 1 ; } } return cache[n - 1 ]; } // Drivers code public static void main(String[] args) { int n = 4 ; int arr[] = { 1 , 2 , 3 , 3 }; int time[] = { 1 , 2 , 3 , 4 }; // Function Call System.out.println(totalTime(n, arr, time)); } } |
Python3
# Python3 code for the approach # Funciton to find minimum time to pick # all elements with a cooldown period def totalTime(n, arr, time): # create a hashmap to store the last occurrence of each task hm = {} # create a list to store the cache for each task cache = [ 0 ] * n # initialize the hashmap and cache for the first task hm[arr[ 0 ]] = 0 cache[ 0 ] = 0 # loop through each task starting from the second one for i in range ( 1 , n): # if the current task has been seen before if arr[i] in hm: # calculate the current time and previous time for the task current_time = cache[i - 1 ] + 1 previous_time = cache[hm[arr[i]]] # calculate the amount of time the task has waited waited = current_time - previous_time # if the task has waited less than its time requirement, # update the current time if waited < time[arr[i] - 1 ]: current_time + = time[arr[i] - 1 ] - waited # update the cache and hashmap for the current task cache[i] = current_time hm[arr[i]] = i # if the current task has not been seen before else : # update the cache and hashmap for the current task hm[arr[i]] = i cache[i] = cache[i - 1 ] + 1 # return the total time required for all tasks return cache[n - 1 ] # Driver's code if __name__ = = "__main__" : # Input n = 4 arr = [ 1 , 2 , 3 , 3 ] time = [ 1 , 2 , 3 , 4 ] # Function Call print (totalTime(n, arr, time)) |
C#
// C# program to find total time using System; using System.Collections.Generic; class Program { public static long totalTime( int n, int [] arr, int [] time) { Dictionary< int , int > hm = new Dictionary< int , int >(); long [] cache = new long [n]; hm.Add(arr[0], 0); cache[0] = 0; for ( int i = 1; i < n; i++) { if (hm.ContainsKey(arr[i])) { long currentTime = cache[i - 1] + 1; long previousTime = cache[hm[arr[i]]]; long waited = currentTime - previousTime; if (waited < time[arr[i] - 1]) { currentTime += time[arr[i] - 1] - waited; } cache[i] = currentTime; hm[arr[i]] = i; } else { hm.Add(arr[i], i); cache[i] = cache[i - 1] + 1; } } return cache[n - 1]; } static void Main( string [] args) { int n = 4; int [] arr = { 1, 2, 3, 3 }; int [] time = { 1, 2, 3, 4 }; Console.WriteLine(totalTime(n, arr, time)); } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript Program for the approach function totalTime(n, arr, time) { const hm = new Map(); const cache = new Array(n).fill(0); hm.set(arr[0], 0); cache[0] = 0; for (let i = 1; i < n; i++) { if (hm.has(arr[i])) { let currentTime = cache[i - 1] + 1; let previousTime = cache[hm.get(arr[i])]; let waited = currentTime - previousTime; if (waited < time[arr[i] - 1]) { currentTime += time[arr[i] - 1] - waited; } cache[i] = currentTime; hm.set(arr[i], i); } else { hm.set(arr[i], i); cache[i] = cache[i - 1] + 1; } } return cache[n - 1]; } const n = 4; const arr = [1, 2, 3, 3]; const time = [1, 2, 3, 4]; console.log(totalTime(n, arr, time)); // This code was contributed by codearcade |
5
Time Complexity: O(N)
Auxiliary Space: O(N)