You are given an array products, where products[i] is the type of the i-th product that 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 those 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 such as:
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.