Find Minimum Days With Cooling
Problem: Minimum Days With Cooling
You are given an array products, where products[i] represents the type of the i-th product that must be manufactured. Products must be manufactured in the exact order given. Manufacturing one product takes exactly 1 day.
After producing a product of type x, you must wait at least space full days before producing type x again. During these waiting days, you may either produce other product types if they are next in the required order, or stay idle.
Return the minimum number of days required to finish producing all products.
Implement a function with the signature:
def min_days(products: List[int], space: int) -> int
Example:
- Input:
products = [1, 3, 1, 3, 2],space = 2 - Output:
6
One optimal schedule is:
- Day 1: produce
1 - Day 2: produce
3 - Day 3: idle
- Day 4: produce
1 - Day 5: produce
3 - Day 6: produce
2
Assume len(products) can be large, so an O(n) solution is preferred.
AI interview prep
Core dilemma
Optimizing a sequence of dependent tasks (product manufacturing with cooldowns) to minimize total completion time, often requiring a greedy strategy to manage resource contention (product type availability).
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Find Minimum Days With Cooling
Problem: Minimum Days With Cooling
You are given an array products, where products[i] represents the type of the i-th product that must be manufactured. Products must be manufactured in the exact order given. Manufacturing one product takes exactly 1 day.
After producing a product of type x, you must wait at least space full days before producing type x again. During these waiting days, you may either produce other product types if they are next in the required order, or stay idle.
Return the minimum number of days required to finish producing all products.
Implement a function with the signature:
def min_days(products: List[int], space: int) -> int
Example:
- Input:
products = [1, 3, 1, 3, 2],space = 2 - Output:
6
One optimal schedule is:
- Day 1: produce
1 - Day 2: produce
3 - Day 3: idle
- Day 4: produce
1 - Day 5: produce
3 - Day 6: produce
2
Assume len(products) can be large, so an O(n) solution is preferred.