Solar Cleaning Voucher Selection
Lexicographically smallest maximum-value indices from value and deadline arrays
A solar farm has received cleaning vouchers for its panel banks. Voucher i produces an additional energy[i] units of energy if it is used no later than day deadlines[i].
The cleaning robot can use at most one voucher per day, starting on day 1. Each voucher takes one whole day, can be used only once, and may be used on any day from 1 through its deadline, inclusive. Vouchers may be used in any order, and unused vouchers are allowed.
Choose a feasible set of vouchers that maximizes the total additional energy. Return the chosen voucher indices in increasing order.
If multiple sets achieve the maximum energy, return the lexicographically smallest increasing list of indices. To compare two lists lexicographically, use their first differing element; if one is a prefix of the other, the shorter list is smaller.
If there are no vouchers, return an empty list.
Examples
Example 1
Input: energy = [9,6,12,5], deadlines = [1,1,2,2] Output: [0,2]
Vouchers 0 and 2 can be used on days 1 and 2. Their combined energy is greater than that of any other feasible selection. Vouchers 0 and 1 cannot both be used because both expire on day 1.
Example 2
Input: energy = [8,8,8], deadlines = [1,2,1] Output: [0,1]
Exactly two vouchers can be used. Several selections have the same total energy, so the increasing index lists determine the winner: selecting vouchers 0 and 1 gives the lexicographically smallest one.
Example 3
Input: energy = [4,10,7], deadlines = [3,1,2] Output: [0,1,2]
All three vouchers can be used before their deadlines, so none needs to be discarded. Return their indices in increasing order, not in execution order.
Constraints
- 0 <= energy.length <= 4000
- deadlines.length == energy.length
- 1 <= energy[i] <= 1000000
- 1 <= deadlines[i] <= energy.length for every voucher
The intended solution takes O(n log n) time and O(n) auxiliary space. All energy values are positive. Deadline constraints form nested capacity limits; the heap's index tie-break produces the required canonical optimal selection.
Hints
Show hint 1Hint 1
Process vouchers in nondecreasing deadline order. After considering a voucher expiring on day d, at most d of the considered vouchers can be retained.
Show hint 2Hint 2
If too many vouchers are retained, discard one with the smallest energy. Among equal-energy candidates, discard the largest index so that earlier indices remain preferred.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the algorithm change if the robot could use up to c vouchers each day?
- How could you also return an explicit valid execution day for every selected voucher?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem