Compute maximum distinct-product pickup days

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.

Maximum Distinct-Product Pickup Days

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)

Examples

Example 1

Input: quantities = [2,1]
Output: 2

Explanation: Day 1: pick from the product with 2 -> [1,1]. Day 2: pick both -> [0,0]. Day 3 requires 3 distinct products but none remain; answer is 2.

Example 2

Input: quantities = [6,6,6,1,1,1]
Output: 5

Explanation: Greedily picking the largest counts each day yields 5 days. On day 6, only 3 products remain positive, so it is impossible to pick 6 distinct products.

Hints

1. On day d you need at least d products with positive remaining quantities.
2. Greedily take one unit from the d largest available quantities each day.
3. A max-heap efficiently retrieves the largest counts at each step.
4. Stop when the heap has fewer than d elements.

Approach

Use a max-heap (priority queue) to always pick from the largest remaining quantities, preserving as many positive counts as possible for future days. On day d, if fewer than d positive quantities remain, no valid selection exists and the process stops. Otherwise, pop the top d counts, decrement each by 1, and push back any that remain positive. This greedy strategy is optimal by exchange: replacing any pick from a smaller count with a larger one cannot reduce future feasibility because it keeps the number of positive entries at least as high as before.

• Time complexity: O(S log n), where S = sum(quantities) and n = len(quantities)
• Space complexity: O(n)