Compute Minimum Production Days
Company: Interactive
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
You are given a list of product IDs `products`, where `products[i]` is the type of the product that must be produced at step `i`, and a non-negative integer `space` representing a required cooling period.
Rules:
- You can produce at most one product per day.
- The products must be produced in the given order.
- After producing a product with type `x` on day `d`, you must wait at least `space` full days before producing type `x` again. In other words, the next valid day to produce the same type is `d + space + 1`.
- During waiting days, you may either produce the next product in order (if it is valid to produce) or stay idle.
Write a function that returns the minimum number of days needed to produce all products in the given order:
```python
def min_days(products: List[int], space: int) -> int
```
**Example**
- Input: `products = [1, 3, 1, 3, 2]`, `space = 2`
- Output: `6`
One optimal schedule:
- Day 1: produce `1`
- Day 2: produce `3`
- Day 3: idle
- Day 4: produce `1`
- Day 5: produce `3`
- Day 6: produce `2`
So the minimum total number of days is `6`.
Assume `len(products)` can be large, so an `O(n)` solution is preferred.
Quick Answer: A data engineering coding screen on greedy scheduling under a cooldown constraint: produce an ordered list of products, one per day, where each product type must cool down for `space` days before it can be produced again. Candidates must return the minimum number of days, ideally in O(n) time using a hash map of last-produced days.
You are given a list of product IDs `products`, where `products[i]` is the type of the product that must be produced at step `i`, and a non-negative integer `space` representing a required cooling period.
Rules:
- You can produce at most one product per day.
- The products must be produced in the given order.
- After producing a product with type `x` on day `d`, you must wait at least `space` full days before producing type `x` again. In other words, the next valid day to produce the same type is `d + space + 1`.
- During waiting days, you may either produce the next product in order (if it is valid to produce) or stay idle.
Return the minimum number of days needed to produce all products in the given order.
Example:
- Input: `products = [1, 3, 1, 3, 2]`, `space = 2`
- Output: `6`
One optimal schedule: 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.
Constraints
- 0 <= len(products) <= 10^6
- 0 <= space <= 10^9
- Each products[i] is an integer product-type id
- Products must be produced strictly in the given order
Examples
Input: ([1, 3, 1, 3, 2], 2)
Expected Output: 6
Explanation: The worked example: 1,3 on days 1-2, an idle day 3 while type 1 cools, then 1,3,2 on days 4-6.
Input: ([], 3)
Expected Output: 0
Explanation: No products to produce, so zero days are needed.
Hints
- Because the order is fixed, delaying a job that could be produced now can never reduce the total time. So schedule every product on the earliest legal day.
- Track the day the most recent job was scheduled (`day`) and, per product type, the last day that type was produced (`last_day[p]`).
- For each product p the earliest valid day is max(day + 1, last_day[p] + space + 1). Update day and last_day[p] to that value, then move on.