Box Office Refund Queue
Lexicographically first array index order minimizing weighted completion cost
A theater's box office has one clerk and a batch of refund requests ready at time zero. Request i takes durations[i] minutes to process. Once the clerk starts a request, it must be finished before another request starts.
Until request i is finished, the theater accumulates compensation for that request at a rate of rates[i] cents per minute. Thus, if it finishes at time C[i], its compensation cost is rates[i] * C[i].
The clerk processes every request, starting at time zero with no idle time between requests. You may choose their order.
Return a list of the zero-based request indices in an order that minimizes the total compensation cost. If multiple orders achieve the minimum cost, return the lexicographically smallest index list: at the first position where two lists differ, the list containing the smaller index is smaller.
If there are no requests, return an empty list.
Examples
Example 1
Input: durations = [2,5,1], rates = [1,10,1] Output: [1,2,0]
The second request accumulates compensation much faster than the first, so processing it first saves more than processing the shortest request first.
Example 2
Input: durations = [3,1,2], rates = [6,2,4] Output: [0,1,2]
All requests have the same compensation rate per unit of processing time. Every order has the same total cost, so the index tie-breaking rule determines the order.
Example 3
Input: durations = [1,4,2,3], rates = [0,8,0,3] Output: [1,3,0,2]
Requests with positive compensation rates should finish before requests whose rates are zero. The zero-rate requests are ordered by index to resolve their tie.
Constraints
- 0 <= durations.length <= 4500
- rates.length == durations.length
- 1 <= durations[i] <= 1000
- 0 <= rates[i] <= 1000
- All durations and rates are integers.
Use integer cross-products rather than floating-point division when comparing requests. Sorting takes O(n log n) time; the returned index list uses O(n) space.
Hints
Show hint 1Hint 1
Compare two schedules that differ only in the order of two adjacent requests. Which parts of the total cost change?
Show hint 2Hint 2
Compare requests i and j using durations[i] * rates[j] and durations[j] * rates[i]. Use their indices when these products are equal.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you compute the minimum total compensation cost along with the optimal order?
- Would the same ordering rule remain optimal if requests became available at different times? Give a counterexample or a justification.
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