Compute Minimum Production Days
Problem Description
You are tasked with scheduling the production of a sequence of products, given a list of product IDs and a mandatory cooling period.
You will be provided with:
products: A list of integers, whereproducts[i]represents the ID of the product that must be produced at stepi. The products must be produced in this exact order.space: An integer representing the minimum number of full days that must pass between producing the same product ID.
Production Rules
- One Product Per Day: At most one product can be produced per day.
- Sequential Production: Products must be produced strictly in the order specified by the
productslist. - Cooling Period: After producing a product with ID
x, you must wait at leastspacefull days before you can produce productxagain. - Flexibility During Wait: During days when a specific product
xcannot be produced due to its cooling period, you may choose to either produce the next available product in the sequence (if it's notxand is valid to produce) or remain idle.
Objective
Determine the minimum total number of days required to produce all products in the given products list, adhering to all specified rules.
Example
products = [1, 3, 1, 3, 2]space = 2
Output: 6
Explanation:
- Day 1: Produce
1(products remaining:[3, 1, 3, 2]) - Day 2: Produce
3(products remaining:[1, 3, 2]) - Day 3: Idle (Product
1cannot be produced yet due tospace=2. It was produced on Day 1, so it can only be produced again on Day 1 + 2 + 1 = Day 4 earliest. Product3was produced on Day 2, so it can only be produced again on Day 2 + 2 + 1 = Day 5 earliest. The next product is1, which is not available.) - Day 4: Produce
1(products remaining:[3, 2]) - Day 5: Produce
3(products remaining:[2]) - Day 6: Produce
2(products remaining:[])
Total days: 6.
AI interview prep
Core dilemma
Efficiently managing the cooling periods for multiple product types while strictly adhering to sequential production and minimizing total production days. The core conflict is between immediate production opportunities and future constraints imposed by the cooling period.
2 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Compute Minimum Production Days
Problem Description
You are tasked with scheduling the production of a sequence of products, given a list of product IDs and a mandatory cooling period.
You will be provided with:
products: A list of integers, whereproducts[i]represents the ID of the product that must be produced at stepi. The products must be produced in this exact order.space: An integer representing the minimum number of full days that must pass between producing the same product ID.
Production Rules
- One Product Per Day: At most one product can be produced per day.
- Sequential Production: Products must be produced strictly in the order specified by the
productslist. - Cooling Period: After producing a product with ID
x, you must wait at leastspacefull days before you can produce productxagain. - Flexibility During Wait: During days when a specific product
xcannot be produced due to its cooling period, you may choose to either produce the next available product in the sequence (if it's notxand is valid to produce) or remain idle.
Objective
Determine the minimum total number of days required to produce all products in the given products list, adhering to all specified rules.
Example
products = [1, 3, 1, 3, 2]space = 2
Output: 6
Explanation:
- Day 1: Produce
1(products remaining:[3, 1, 3, 2]) - Day 2: Produce
3(products remaining:[1, 3, 2]) - Day 3: Idle (Product
1cannot be produced yet due tospace=2. It was produced on Day 1, so it can only be produced again on Day 1 + 2 + 1 = Day 4 earliest. Product3was produced on Day 2, so it can only be produced again on Day 2 + 2 + 1 = Day 5 earliest. The next product is1, which is not available.) - Day 4: Produce
1(products remaining:[3, 2]) - Day 5: Produce
3(products remaining:[2]) - Day 6: Produce
2(products remaining:[])
Total days: 6.