Topic 11 of 15
Greedy
Grabbing the best candy first.
Greedy means: at every step, take the choice that looks best right now, and never undo it. It only works when you can prove that the best move now never hurts later. Usually the trick is to sort first, by end time, by value per weight, or by deadline.
What you will be able to do
Sort then pickInterval schedulingExchange argument proofsHeaps for the best next choiceWhen greedy fails and DP is needed
0/35
Meet the greedy choice
01 / 04
Five meetings, one room. Which ones fit without overlapping?
- done
- answer
- rejected
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Activity Selection ProblemFit as many play dates as you can into one afternoon by always picking the one that ends soonest.Greedy by sorting
- 02Job Sequencing ProblemPick which one-hour chores to do before their deadlines so you earn the most pocket money.Greedy by sorting
- 03Huffman CodingGive common letters short secret codes and rare letters long ones by always joining the two rarest groups first.Greedy with a min heap
- 04Water Connection ProblemHouses are joined by one-way pipes into chains, so put a tank at the start of each chain, a tap at its end, and report the narrowest pipe on the way.Following chains in a graph
- 05Fractional Knapsack ProblemFill a bag that can only carry so much by taking the most valuable stuff per kilo first, cutting the last piece to fit.Greedy by sorting
- 06Greedy Algorithm to find Minimum number of CoinsPay an amount with the fewest coins and notes by always handing over the biggest one that still fits.Greedy by sorting
- 07Maximum trains for which stoppage can be providedEach train wants one fixed platform, so on every platform let in the train that leaves first and count how many trains can stop.Greedy by earliest finish
- 08Minimum Platforms ProblemFind how many platforms a station needs so no train waits, by walking through the day and counting trains that are in the station at the same time.Sweep line with two pointers
- 09Buy Maximum Stocks if i stocks can be bought on i-th dayBuy as many shares as your money allows when day i lets you buy at most i shares, by shopping the cheapest days first.Greedy by sorting
- 10Find the minimum and maximum amount to buy all N candiesWith a buy one, get K free deal, find the least and the most you could pay to take home every candy in the shop.Greedy by sorting
- 11Minimize Cash Flow among a given set of friends who have borrowed money from each otherFriends owe each other money in a tangle of IOU notes, so work out who is up and who is down overall and settle with as little money moving as possible.Greedy with two heaps
- 12Minimum Cost to cut a board into squaresCut a board into little squares where every cut costs its line price times the pieces it passes through, by making the expensive cuts first.Greedy by sorting
- 13Check if it is possible to survive on IslandStuck on an island where the only shop shuts on Sundays, find the fewest shopping days that keep you fed, or say it cannot be done.Greedy math
- 14Find maximum meetings in one roomBook as many meetings as possible into one room by always taking the meeting that ends first.Greedy by sorting
- 15Maximum product subset of an arrayPick a team of number cards whose product is as big as possible, by keeping minus cards in pairs and leaving out zeros.Counting and case analysis
- 16Maximize array sum after K negationsYou must flip the sign of a card exactly k times, so flip the worst negative cards first and waste any spare flips on the smallest card.Greedy by sorting
- 17Maximize the sum of arr[i] times iPut number cards into numbered boxes that multiply them, and win the most points by giving the biggest card the biggest box.Greedy by sorting
- 18Maximum sum of absolute difference of an arrayArrange numbers in a ring so neighbours differ as much as possible, by taking from the small end and the big end in turns.Two pointers
- 19Maximize sum of consecutive differences in a circular arraySeat numbers around a round table so that neighbours are as different as possible, by putting small and big numbers in turns.Greedy by sorting
- 20Minimum sum of absolute difference of pairs of two arraysPair up two lists of numbers so the pairs are as close as possible, by sorting both lists and matching them in order.Greedy by sorting
- 21Program for Shortest Job First (or SJF) CPU SchedulingDecide which job the computer runs next by always picking the shortest job that is already waiting, and work out how long jobs wait on average.Greedy with a min-heap
- 22Program for Least Recently Used (LRU) Page Replacement algorithmKeep only a few pages on a small shelf and, when it is full, throw out the page nobody has used for the longest time, then count the misses.Hash map plus doubly linked list
- 23Smallest subset with sum greater than all other elementsGrab the fewest candy bags so that you hold more candy than all the bags you left behind, by grabbing the biggest bags first.Greedy by sorting
- 24Chocolate Distribution ProblemGive one chocolate packet to each kid so the biggest and smallest packets handed out are as close as possible.Sliding window
- 25DEFKIN - Defense of a KingdomTowers guard their whole row and column, and you find the biggest field that no tower can see by looking for the widest and tallest gaps.Greedy by sorting
- 26DIEHARD - DIE HARDHop between air, water and fire to stay alive as long as possible, by visiting air every other step and picking the gentler of the other two.Greedy simulation
- 27GERGOVIA - Wine trading in GergoviaHouses on one street buy and sell wine, and you find the least carrying work by walking the street once with a running balance.Prefix sum greedy
- 28Picking Up ChicksGet k chicks into the barn on time with the fewest lifts over slow chicks, by saving the fast chicks closest to the barn first.Greedy from the far end
- 29CHOCOLA - ChocolateSnap a chocolate bar into single squares for the least total price by making the expensive snaps first, while they cross the fewest pieces.Greedy by sorting
- 30ARRANGE - Arranging AmplifiersLine up power-raising boxes so a signal comes out as huge as possible: ones first, then biggest to smallest, with one sneaky swap.Greedy by sorting
- 31K Centers ProblemBuild k fire stations so the town that is farthest from any station is as close as possible, using a fast pick-the-worst-off-town trick.Greedy farthest first
- 32Minimum Cost of ropesTie ropes together into one long rope, where each knot costs the length of the two ropes, by always tying the two shortest ropes.Greedy with a min-heap
- 33Find smallest number with given number of digits and sum of digitsBuild the smallest number with a set count of digits and a set digit total by stuffing 9s at the back and keeping the front tiny.Greedy digit building
- 34Rearrange characters in a string such that no two adjacent are sameReorder the letters of a word so that no two equal letters touch, by always writing the letter with the most copies left that was not just used.Greedy with a max-heap
- 35Find maximum sum possible equal sum of three stacksLift blocks off the tops of three towers until all three towers weigh the same, keeping them as tall as possible.Greedy with three pointers