Shopping on a Budget
Medium · rating 1350 · greedy, sorting
You have a fixed budget. The first line contains the number of items n and your budget b. The second line contains n prices. Print the maximum number of items you can afford (buying the cheapest first, each item at most once).
Constraints: 1 ≤ n ≤ 105
Editorial
Shopping on a Budget asks for the maximum number of items you can buy without exceeding a budget — a textbook greedy problem.
Approach
To fit the most items, always buy the cheapest one available. Sort prices ascending and take them while the budget holds, stopping at the first you can't afford.
prices.sort()
spent = count = 0
for p in prices:
if spent + p > budget: break
spent += p; count += 1
return countWhy greedy is optimal
Any optimal set of k items can be swapped cheapest-for-cheapest into the k lowest-priced items without raising the cost — so taking the cheapest first never loses.
Complexity
Time: O(n log n). Space: O(1).