Book the most events
The café's one room has many booking requests. To fit the most, always accept the booking that ends earliest among those that still fit. A greedy algorithm makes the locally best choice and never looks back — fast and simple, but only correct when you can prove the choice is safe.
When greedy works — and when it doesn't
function maxBookings(requests) {
const sorted = [...requests].sort((a, b) => a.end - b.end);
const chosen = [];
let freeAt = -Infinity;
for (const r of sorted) {
if (r.start >= freeAt) {
chosen.push(r.name);
freeAt = r.end;
}
}
return chosen;
}
console.log(maxBookings([
{ name: "yoga", start: 9, end: 12 },
{ name: "book club", start: 10, end: 11 },
{ name: "chess", start: 11, end: 13 },
{ name: "music", start: 12, end: 15 },
{ name: "art", start: 14, end: 16 },
]));
function greedyCoins(amount, coins) {
const used = [];
for (const c of [...coins].sort((a, b) => b - a)) while (amount >= c) { amount -= c; used.push(c); }
return used;
}
console.log(greedyCoins(30, [25, 10, 1]));
console.log(greedyCoins(30, [25, 10, 1]).length, "coins — but 10+10+10 needs only 3");