Other classic greedy — buy max stocks, candy cost, survive on island, wine trading, amplifiers, K centers, defense of a kingdom
Problem
A set of short greedy puzzles:
Buy maximum stocks — on day i you may buy at most i shares at price[i] with a fixed budget. Candy store — for every candy you buy, you get up to k others free; find the minimum and maximum total cost. Survive on an island — food lasts s days and the shop is shut on Sundays. Wine trading (GERGOVIA) — houses buy or sell wine, and moving one bottle one house costs 1. Arranging amplifiers — order the numbers to maximise a tower of powers. K centres — choose k cities to minimise the largest distance to the nearest centre. Defense of a kingdom — find the largest rectangle with no tower in its row or column.
Example 1
Input: buy stocks: price = [10, 7, 19], budget = 45 Output: 4
Buy 1 at 10 (day 1) and 2 at 7 (day 2) = 24, then 1 at 19.
Also asked as: Buy Maximum Stocks if i stocks can be bought on i-th day · Find the minimum and maximum amount to buy all N candies · Check if it is possible to survive on Island · GERGOVIA -Wine trading in Gergovia · ARRANGE -Arranging Amplifiers · K Centers Problem · DEFKIN -Defense of a Kingdom · DIEHARD -DIE HARD · Picking Up Chicks · Smallest subset with sum greater than all other elements · Minimum sum of absolute difference of pairs of two arrays · Program for Shortest Job First (or SJF) CPU Scheduling
Test cases
Case 1
Input: [5,-4,1,-3,1] Expected: "9"
Case 2
Input: [-1000,-1000,-1000,1000,1000,1000] Expected: "9000"
Case 3
Input: [1,-1] Expected: "1"
Case 4
Input: [0] Expected: "0"
View solutionHide solution1 approach
1. Common patterns
Time mostly O(n log n)Space O(n)
Buy max stocks: sort (price, day) ascending by price; on each day buy as many as the day index allows within budget. Candy cost (buy 1 free K): sort; min = sum of the cheapest ceil(n/(k+1)), max = sum of the most expensive ceil(n/(k+1)). Survive on island: feasible iff daily food ≤ what you can buy per allowed shopping day; then greedily buy the maximum on shopping days. Wine trading (Gergovia): scan the street carrying a running surplus/deficit; cost += |carry| each step. Arranging amplifiers: to maximise a tower of exponents, put the largest base at the bottom and sort the rest ascending (compare via logs). K centers: repeatedly place a center at the point farthest from all existing centers (2-approximation). Defense of a kingdom: the largest undefended rectangle = (max gap between adjacent tower columns) × (max gap between adjacent tower rows). Smallest subset with sum > rest: sort descending and take the largest elements until their sum exceeds half the total. Min sum of |a[i]−b[i]|: sort both arrays and pair them index-by-index. SJF: sort by burst time; average waiting time = running prefix of bursts.
// Wine trading in Gergovia — total transport costfunction gergovia(demands) { // + = wants to buy, - = wants to sell let carry = 0n, cost = 0n; for (const d of demands) { carry += BigInt(d); cost += carry < 0n ? -carry : carry; } return cost.toString();}
// Smallest subset whose sum exceeds the restfunction smallestSubsetOverHalf(a) { a.sort((x, y) => y - x); const total = a.reduce((s, v) => s + v, 0); let acc = 0, k = 0; for (const v of a) { acc += v; k++; if (acc > total - acc) break; } return k;}