Basic Greedy Questions

1. Maximum activities you can attend

Problem. You have n activities, each with a start and end time. You can attend one at a time. Find the maximum number you can attend.

Activities: [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]

What’s the right sort criterion? What’s the answer?

2. Coin change with US denominations

Problem. You have unlimited coins of values {1, 5, 10, 25}. What’s the minimum number of coins needed to make 87 cents?

3. Fractional knapsack

Problem. A knapsack has capacity 50 kg. Items: [(weight=10, value=60), (20, 100), (30, 120)]. You can take fractions of any item. Maximize value.

4. Minimum number of platforms

Problem. A train station serves trains with arrival and departure times. Find the minimum number of platforms needed so no train ever has to wait.

Trains: arrivals [900, 940, 950, 1100, 1500, 1800], departures [910, 1200, 1120, 1130, 1900, 2000].

5. The greedy proof challenge

Problem. Someone claims this greedy works for 0/1 knapsack (take-or-leave whole items): “Sort by value-per-weight ratio descending. Take each item if it fits.”

Find a counter-example.

6. Assign cookies

Problem. You have n children with greed factors g[i] (the minimum cookie size each child wants). You have m cookies with sizes s[j]. Each child gets at most one cookie. Maximize the number of content children.

g = [1, 2, 3], s = [1, 1]