Given a 2D integer array, machines[][], where each machine[i] represents [Mi, Ms], where Mi is the time required for the machine to produce its first product, and Ms is the increment in time for each additional product. In other words, the ith machine can finish producing the x’th product in Mi * Ms^{ ( x – 1) } seconds. Also, provided is an integer (changeTime), the time required to switch between machines. The task is to determine the minimum time required to manufacture the total number of products(totalProduct).
For example, if Mi = 3 and Ms = 2, then the machine would finish its 1st product in 3 seconds ( 3*21-1 ), its 2nd product in 3 * 2 = 6 seconds ( 3*22-1 ), its 3rd product in 3 * 4 = 12 seconds ( 3*23-1 ), and so on.
Examples:
Input: machines = [[3, 100], [5, 2]], changeTime = 1, totalProduct = 3
Output: 11
Explanation: Product 1: Start with Machine 0 and finish one Product in 3 seconds.
Product 2: Change Machine to a new Machine 0 for 1 second and then finish the second Product in another 3 seconds.
Product 3: Change the Machine to a new Machine 0 for 1 second and then finish the third Product in another 3 seconds.
Total time = 3 + 1 + 3 + 1 + 3 = 11 seconds.
The minimum time to complete the Manufacturing is 11 seconds.Input: machines = [[2, 3], [3, 4]], changeTime = 5, totalProduct = 4
Output: 21
Explanation: Product 1: Start with Machine 0 and finish a Product in 2 seconds.
Product 2: Continue with Machine 0 and finish the next Product in 2 * 3 = 6 seconds.
Product 3: Change Machine to a new Machine 0 for 5 seconds and then finish next Product in another 2 seconds.
Product 4: Continue with Machine 0 and finish the next Product in 2 * 3 = 6 seconds.
Total time = 2 + 6 + 5 + 2 + 6 = 21 seconds.
The minimum time to complete the Manufacturing is 21 seconds.Input: machines = [[1, 10], [2, 2], [3, 4]], changeTime = 6, totalProduct = 5
Output: 25
Explanation: Product 1: Start with Machine 1 and finish a Product in 2 seconds.
Product 2: Continue with Machine 1 and finish the next Product in 2 * 2 = 4 seconds.
Product 3: Change Machine to a new Machine 1 for 6 seconds and then finish next Product in another 2 seconds.
Product 4: Continue with Machine 1 and finish the next Product in 2 * 2 = 4 seconds.
Product 5: Change Machine to new Machine 0 for 6 seconds then finish next Product in another 1 second.
Total time = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 seconds.
The minimum time to complete the Manufacturing is 25 seconds.
Approach: To solve the problem follow the below idea:
The given problem can be solved using dynamic programming. We can maintain an array dp, where dp[i] represents the minimum time required to finish the i-th product. We can update dp[i] for each machine by considering the time required to finish the i-th product using that machine and the minimum time required to finish the (i-1)-th product. After updating dp[i] for all machines, we can update dp[i] again by considering the time required to change the machine optimally.
Tabulation:
- Precompute a table, DP[i], which stores the minimum time to complete ith product without change of machine. Now the problem becomes: when should we change machine to new one to minimize the total time?
- We just need to know how many products we can manufacture before first change, j, and solve the remaining subproblem, which is stored in, dp[i – j].
- Once we select our machine (outer for each loop), we try to keep it for the remaining product (inner for loop). After each product with the same machine, we try to change to a new one and continue the race for the remaining product (recursive call). We’ll bubble up the minimum from each recursive call. The minimum of minimums will be the answer.
- dp[i] = min( f[i] # no machine change, min(f[j] + change_time + dp[i – j], for j < i) # change after the j first products )
Steps that were to follow the above approach:
- Initialize a vector dp of size numProduct + 1 with 1e9 (a very large value).
- Iterate over each machine in the given vector machine.
- For each machine, initialize lapTime and totTime to the first element of that machine.
- For i from 1 to numProduct, update dp[i] with the minimum of dp[i] and totTime.
- Multiply lapTime by the second element of the machine for each iteration of i, and add it to totTime.
- If totTime exceeds 1e9, break out of the loop.
- Iterate over i from 2 to numProduct.
- Iterate over j from 1 to i – 1.
- Update dp[i] with the minimum of dp[i], dp[j] + changeTime + dp[i-j].
- Return dp[numProduct] as the minimum time required to finish all the products.
Below is the implementation for the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum timeint minimumFinishTime(vector<vector<int> >& machine, int changeTime, int numProduct){ vector<int> dp(numProduct + 1, 1e9); for (auto& t : machine) { // Lapse time for each machine. long long lapTime = t[0]; // Total time currently. long long totTime = t[0]; for (int i = 1; i <= numProduct; i++) { // Comparing total time // currently and current // minimum at this index // of dp. dp[i] = min(dp[i], (int)totTime); // ProductTime multiplying by // Ms each time totTime adding // up each time by ProductTime. if ((totTime += (lapTime *= t[1])) > 1e9) { break; } } } // Updating each dp index with minimum // of current dp value and changing // machine optimally. for (int i = 2; i <= numProduct; i++) { for (int j = 1; j < i; j++) { dp[i] = min(dp[i], dp[j] + changeTime + dp[i - j]); } } return dp[numProduct];}// Driver's codeint main(){ vector<vector<int> > machine = { { 3, 100 }, { 5, 2 } }; int changeTime = 1; int Products = 3; // Function call cout << "Minimum time to finish the product : " << minimumFinishTime(machine, changeTime, Products); return 0;} |
Java
import java.util.Arrays;public class GFG { public static int minimumFinishTime(int[][] machine, int changeTime, int numProduct) { // Initialize a dynamic programming array dp with // Integer.MAX_VALUE int[] dp = new int[numProduct + 1]; Arrays.fill(dp, Integer.MAX_VALUE); // Iterate over each machine for (int[] t : machine) { // Lapse time for each machine int lapTime = t[0]; // Total time currently int totTime = t[0]; for (int i = 1; i <= numProduct; i++) { // Comparing total time currently and // current minimum at this index of dp dp[i] = Math.min(dp[i], totTime); // Multiplying the lap time by the machine // speed for each product and adding it to // the total time If the total time exceeds // 1e9, break the loop if (totTime + (lapTime * t[1]) > 1e9) { break; } totTime += lapTime * t[1]; // Update the total time lapTime *= t[1]; // Update the lap time } } // Updating each dp index with the minimum of // current dp value and changing machine optimally for (int i = 2; i <= numProduct; i++) { for (int j = 1; j < i; j++) { dp[i] = Math.min(dp[i], dp[j] + changeTime + dp[i - j]); } } // Return the minimum time required to finish all // products return dp[numProduct]; } public static void main(String[] args) { // Initialize machine array, change time and number // of products int[][] machine = { { 3, 100 }, { 5, 2 } }; int changeTime = 1; int numProduct = 3; // Call the function and print the minimum time System.out.println( "Minimum time to finish the product: " + minimumFinishTime(machine, changeTime, numProduct)); }} |
Python3
# Function to return the minimum timedef minimumFinishTime(machine, changeTime, numProduct): # Initialize a dynamic programming list dp with infinite values dp = [float('inf')] * (numProduct + 1) # Iterate over each machine for t in machine: # Lapse time for each machine lapTime = t[0] # Total time currently totTime = t[0] # Iterate over each product for i in range(1, numProduct + 1): # Comparing total time currently and current minimum at this index of dp dp[i] = min(dp[i], totTime) # Multiplying the lap time by the machine speed for each product and adding it to the total time # If the total time exceeds 1e9, break the loop if (totTime + (lapTime * t[1])) > 1e9: break totTime += lapTime * t[1] # Update the total time lapTime *= t[1] # Update the lap time # Updating each dp index with the minimum of current dp value and changing machine optimally for i in range(2, numProduct + 1): for j in range(1, i): dp[i] = min(dp[i], dp[j] + changeTime + dp[i - j]) # Return the minimum time required to finish all products return dp[numProduct]# Driver's codemachine = [[3, 100], [5, 2]]changeTime = 1numProduct = 3# Function callprint("Minimum time to finish the product: ", minimumFinishTime(machine, changeTime, numProduct))# Code contributed by Siddharth Aher |
C#
using System;class Program { static int minimumFinishTime(int[][] machine, int changeTime, int numProduct) { // Initialize a dynamic programming array dp with // Integer.MAX_VALUE int[] dp = new int[numProduct + 1]; for (int i = 0; i < dp.Length; i++) { dp[i] = int.MaxValue; } // Iterate over each machine for (int i = 0; i < machine.Length; i++) { // Lapse time for each machine int lapTime = machine[i][0]; // Total time currently int totTime = machine[i][0]; for (int j = 1; j <= numProduct; j++) { // Comparing total time currently and // current minimum at this index of dp dp[j] = Math.Min(dp[j], totTime); // Multiplying the lap time by the machine // speed for each product and adding it to // the total time If the total time exceeds // 1e9, break the loop if (totTime + (lapTime * machine[i][1]) > 1e9) { break; } totTime += lapTime * machine[i][1]; // Update the // total time lapTime *= machine[i][1]; // Update the lap time } } // Updating each dp index with the minimum of // current dp value and changing machine optimally for (int i = 2; i <= numProduct; i++) { for (int j = 1; j < i; j++) { dp[i] = Math.Min(dp[i], dp[j] + changeTime + dp[i - j]); } } // Return the minimum time required to finish all // products return dp[numProduct]; } static void Main(string[] args) { // Initialize machine array, change time and number // of products int[][] machine = { new int[] { 3, 100 }, new int[] { 5, 2 } }; int changeTime = 1; int numProduct = 3; // Call the function and print the minimum time Console.WriteLine( "Minimum time to finish the product: " + minimumFinishTime(machine, changeTime, numProduct)); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Function to return the minimum timefunction minimumFinishTime(machine, changeTime, numProduct) { // Initialize a dynamic programming array dp with infinite values let dp = new Array(numProduct + 1).fill(Number.POSITIVE_INFINITY); // Iterate over each machine for (let t of machine) { // Lapse time for each machine let lapTime = t[0]; // Total time currently let totTime = t[0]; // Iterate over each product for (let i = 1; i <= numProduct; i++) { // Comparing total time currently and current minimum at this index of dp dp[i] = Math.min(dp[i], totTime); // Multiplying the lap time by the machine speed for each product and adding it to the total time // If the total time exceeds 1e9, break the loop if (totTime + lapTime * t[1] > 1e9) { break; } totTime += lapTime * t[1]; // Update the total time lapTime *= t[1]; // Update the lap time } } // Updating each dp index with the minimum of current dp value and changing machine optimally for (let i = 2; i <= numProduct; i++) { for (let j = 1; j < i; j++) { dp[i] = Math.min(dp[i], dp[j] + changeTime + dp[i - j]); } } // Return the minimum time required to finish all products return dp[numProduct];}// Driver's codelet machine = [ [3, 100], [5, 2]];let changeTime = 1;let numProduct = 3;// Function callconsole.log( "Minimum time to finish the product: " + minimumFinishTime(machine, changeTime, numProduct));// This code is contributed by Prajwal Kandekar |
Minimum time to finish the product : 11
Time Complexity: O(max(totalProducts^2, number of Machines))
Auxiliary Space: O(Products)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
