Compute maximum distinct-product pickup days
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
Given an array of positive integers representing quantities of different products, on day i (starting from
1) you must pick exactly i distinct products, taking one unit from each chosen product. After each pick the chosen products' quantities decrease by 1 and cannot go below 0. Compute the maximum number of days the process can continue.
Quick Answer: This question evaluates a candidate's understanding of greedy and resource-allocation strategies along with combinatorial reasoning to maximize operations under discrete constraints.
You are given an array quantities of positive integers, where quantities[i] is the number of units of product i. Starting from day 1, on day d you must pick exactly d distinct products (if possible), taking one unit from each picked product. After each day's picks, the chosen products' quantities each decrease by 1 and never go below 0. You may choose which products to pick each day to maximize the number of days. Return the maximum number of consecutive days (starting from day 1) the process can continue.
Constraints
- 1 <= len(quantities) <= 2e5
- 1 <= quantities[i] <= 1e9
- Sum of quantities <= 2e5
- Answer is at most len(quantities)
Hints
- On day d you need at least d products with positive remaining quantities.
- Greedily take one unit from the d largest available quantities each day.
- A max-heap efficiently retrieves the largest counts at each step.
- Stop when the heap has fewer than d elements.