Ski Trail Opening Checklist

Max-count array subset indices within budget, least sum then lexicographic order

EasyGreedySorting

A ski resort has one crew preparing trails before opening time. Trail i requires minutes[i] minutes of work. The crew can prepare trails in any order, but only one at a time, and has at most budget minutes available. Every fully prepared trail counts equally; partially preparing a trail does not count.

Return the zero-based indices of the trails the crew should prepare, in increasing order. Choose the set using these priorities, in order:

  1. Prepare as many trails as possible.
  2. Among sets of that size, use the least total preparation time.
  3. If there is still a tie, choose the lexicographically smallest increasing list of indices.

For two different lists of equal length, the lexicographically smaller list has the smaller index at the first position where they differ.

A trail requiring zero minutes can be prepared even when the budget is zero. Return an empty list if no trails can be prepared.

Examples

Example 1

Input: minutes = [8,3,3,6], budget = 9
Output: [1,2]

The two three-minute trails fit together. Preparing three trails would exceed the budget, and this pair uses the least time among all feasible pairs.

Example 2

Input: minutes = [5,2,2,2], budget = 5
Output: [1,2]

Only two trails can be prepared. Any two of the three two-minute trails use the least possible time, so the index tie-break chooses the earliest two.

Example 3

Input: minutes = [0,7,0], budget = 0
Output: [0,2]

Both zero-minute trails can be prepared without spending any of the budget.

Constraints

  • 0 <= minutes.length <= 5000
  • 0 <= minutes[i] <= 1000000
  • 0 <= budget <= 1000000000
  • All values are integers.

The intended solution takes O(n log n) time and O(n) auxiliary space. Input order does not restrict preparation order.

Hints

Show hint 1

For any fixed number of trails, which preparation times give the smallest possible total?

Show hint 2

Sort trails by preparation time, breaking ties by index. Take trails while the next one fits, then put the selected indices in increasing order.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you justify the greedy choice using an exchange argument?
  • If preparation times were restricted to a small integer range, how could you avoid comparison sorting?

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