Other classic greedy — buy max stocks, candy cost, survive on island, wine trading, amplifiers, K centers, defense of a kingdom

Medium

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"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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 cost
function 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 rest
function 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;
}