Greedy Algorithm Exercises: Practice Problems (with Solutions)
Time to practice greedy thinking. For each problem, first decide on a selection rule (“what is best right now?”), then try to break it with a small counterexample before you trust it — that habit is the whole skill from when greedy works. Solve each yourself, then open the linked answer. Every View answer link jumps to a full multi-language solution on the greedy solutions page.
How to practice: Set a timer (15–25 min per problem). If you’re stuck, re-read the greedy introduction. For each one, ask: can I prove this greedy choice is safe, or does it just feel right?
Warm-ups
Q1. Assign Cookies. Each child i has a greed factor g[i] and each cookie j has a size s[j]. A child is content if assigned a cookie with s[j] >= g[i]; each cookie goes to at most one child. Maximize the number of content children. Target O(n log n).
Q2. Fractional Knapsack. Given items with (value, weight) and a capacity W, maximize the total value you can carry. Unlike 0/1 knapsack, you may take fractions of an item. Target O(n log n).
Core problems
Q3. Jump Game. Given an array nums where nums[i] is the maximum jump length from index i, determine whether you can reach the last index starting from index 0. Target O(n) time, O(1) space.
Q4. Gas Station. There are n gas stations in a circle. gas[i] is the fuel available at station i and cost[i] is the fuel needed to drive to station i+1. Return the starting index from which you can complete the full loop, or -1 if impossible. Target O(n).
Q5. Merge Intervals. Given a list of intervals [start, end], merge all overlapping intervals and return the resulting non-overlapping set. Target O(n log n).
Challenge
Q6. Non-overlapping Intervals. Given a set of intervals, return the minimum number you must remove so that the rest do not overlap. Target O(n log n). (Hint: this is activity selection in disguise.)
Q7. Minimum Number of Platforms. Given arrival and departure times of n trains at a station, find the minimum number of platforms needed so that no train waits. Target O(n log n).
Done? Review every solution on the greedy answer sheet — even ones you solved, since the proof of why the rule is safe is the real lesson. Then continue to dynamic programming, where greedy’s failures get fixed.