Most Tasks in a Time Budget
durations[i] is how many minutes task i takes. You have budget minutes in total and may do the tasks in any order, but a task only counts if you finish it completely. Return the largest number of tasks you can finish. If durations is empty, or the budget is too small for even the shortest task, return 0.
Example 1
durations [30,10,50,20]
budget 60
returns 3
The three shortest tasks take 10 + 20 + 30 = 60 minutes, exactly the budget; all four would need 110.
Example 2
durations [100,200]
budget 150
returns 1
Either task alone fits in 150 minutes, both together need 300.
Constraints
0 <= len(durations) <= 1001 <= durations[i] <= 10000 <= budget <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Greedy problems
- Only the Best CountBeginner
- Shortest Walk to SeatsBeginner
- Stepping StonesBeginner
- Third One FreeBeginner
- Two Numbers From Four DigitsBeginner
- Array PartitionEasy
- Assign CookiesEasy
- Best Haul With Partial SacksEasy