14.25 Exercises

Greedy algorithms are best learned by proving, breaking, and implementing them. The code is usually short. The reasoning is where the work happens.

This final section collects exercises that reinforce the patterns from the chapter. Each problem asks you to identify the greedy choice, justify it, implement it, and analyze the result. Several exercises also ask for counterexamples, because a strong greedy designer must know how to disprove bad rules as well as prove good ones.

How to Use These Exercises

For each exercise, work through four steps:

1. State the greedy rule.
2. Prove or disprove the rule.
3. Implement the algorithm.
4. Analyze time and space complexity.

Do not skip the proof step. A greedy algorithm without a proof is only a heuristic.

Exercise 1: Maximum Non-Overlapping Intervals

Given intervals:

[1,3], [2,4], [3,5], [6,8], [7,9]

Select the maximum number of non-overlapping intervals.

Questions:

1. Which sort key should be used?
2. Which intervals are selected?
3. Why does the greedy choice work?
4. What is the time complexity?

Expected direction:

Sort by finish time.
Select the next compatible interval.

Exercise 2: Counterexample for Earliest Start

Show that sorting intervals by earliest start time does not always maximize the number of compatible intervals.

Construct the smallest example you can.

A useful shape is:

One long interval that starts early
Several short intervals that start later

Your answer should include:

• Input intervals
• Greedy output
• Optimal output
• Explanation of the failure

Exercise 3: Fractional Knapsack

Capacity:

W = 70

Items:

Item	Weight	Value
A	20	100
B	30	120
C	40	160
D	10	90

Tasks:

1. Compute value density for each item.
2. Sort items by density.
3. Determine which fractions are taken.
4. Compute total value.
5. Prove why the density rule is safe.

Exercise 4: 0/1 Knapsack Counterexample

Using the same style as fractional knapsack, construct an example where choosing highest density first fails for 0/1 knapsack.

Your example should show:

Greedy value < Optimal value

Explain why the fractional exchange argument no longer applies.

Exercise 5: Job Sequencing with Deadlines

Jobs:

Job	Deadline	Profit
A	2	100
B	1	50
C	2	10
D	1	20
E	3	30

Each job takes one unit of time.

Tasks:

1. Sort jobs by profit.
2. Schedule each job as late as possible before its deadline.
3. Return the final schedule.
4. Compute total profit.
5. Explain why late placement preserves flexibility.

Exercise 6: Minimum Refueling Stops

Input:

target = 100
startFuel = 25

stations = [
    (25, 25),
    (50, 25),
    (75, 25)
]

Tasks:

1. Simulate the max-heap algorithm.
2. Count the minimum number of stops.
3. Explain why choosing the largest passed station is optimal.
4. Modify the input so the destination becomes unreachable.

Exercise 7: Course Scheduling

Courses:

Course	Duration	Deadline
A	5	5
B	4	6
C	2	6
D	1	7

Tasks:

1. Sort by deadline.
2. Add courses one at a time.
3. When total duration exceeds the deadline, remove the longest course.
4. Return the accepted courses.
5. State the invariant maintained by the algorithm.

Exercise 8: Huffman Coding

Frequencies:

Symbol	Frequency
A	5
B	9
C	12
D	13
E	16
F	45

Tasks:

1. Build the Huffman tree manually.
2. Record each merge.
3. Compute the final weighted path length.
4. Explain why the two lowest frequencies can be siblings.
5. Implement the algorithm with a min-heap.

Exercise 9: Remove K Digits

Input:

num = "10200"
k = 1

Tasks:

1. Simulate the monotonic stack.
2. Remove leading zeros from the result.
3. Return the smallest possible number.
4. Explain why popping a larger previous digit is safe.

Then repeat for:

num = "1432219"
k = 3

Exercise 10: Partition Labels

Input:

ababcbacadefegdehijhklij

Tasks:

1. Compute the last occurrence of each character.
2. Scan left to right.
3. Track the current partition boundary.
4. Return the partition lengths.
5. Explain why closing the partition at the boundary is safe.

Exercise 11: Rescue Boats

Input:

people = [3, 2, 2, 1]
limit = 3

Tasks:

1. Sort the weights.
2. Use two pointers.
3. Count the boats.
4. Prove why the heaviest person can be handled immediately.
5. Give a counterexample to the rule "always pair the two lightest people."

Exercise 12: Lemonade Change

Input:

[5, 5, 10, 10, 20]

Tasks:

1. Simulate the algorithm.
2. Determine whether change can be made for every customer.
3. Explain why using 10 + 5 is preferred over 5 + 5 + 5.
4. Give an input where the algorithm fails because change is impossible.

Exercise 13: Minimum Platforms

Arrivals:

900, 940, 950, 1100, 1500, 1800

Departures:

910, 1200, 1120, 1130, 1900, 2000

Tasks:

1. Sort arrivals and departures.
2. Sweep through events.
3. Track active trains.
4. Return the maximum active count.
5. Explain why maximum simultaneous demand is a lower bound and also sufficient.

Exercise 14: Kruskal's Algorithm

Graph edges:

Edge	Weight
A-B	4
A-C	1
B-C	3
B-D	2
C-D	5

Tasks:

1. Sort edges by weight.
2. Use union-find to select safe edges.
3. Return the minimum spanning tree.
4. Compute total weight.
5. Prove correctness using the cut property.

Exercise 15: Dijkstra's Greedy Choice

Given a graph with nonnegative edge weights, explain why the vertex with the smallest tentative distance can be finalized.

Then answer:

1. What breaks if negative edges are allowed?
2. Give a small graph where Dijkstra fails with a negative edge.
3. Which algorithm can handle negative edges?

Exercise 16: Coin Change Counterexample

Coins:

4, 3, 1

Amount:

6

Tasks:

1. Run the largest-coin greedy algorithm.
2. Compute the optimal solution.
3. Explain why the greedy remainder is bad.
4. Find another noncanonical coin system where greedy fails.

Exercise 17: Maximum Units on a Truck

Input:

boxTypes = [
    [5, 10],
    [2, 5],
    [4, 7],
    [3, 9]
]

truckSize = 10

Tasks:

1. Sort by units per box.
2. Load boxes greedily.
3. Compute total units.
4. Prove correctness using an exchange argument.

Exercise 18: Reorganize String

Input:

aaabbc

Tasks:

1. Count character frequencies.
2. Use a max-heap to construct a valid string.
3. Explain why the most frequent character should be used early.
4. Determine when no valid answer exists.

Exercise 19: Greedy or Dynamic Programming?

Classify each problem as usually greedy, dynamic programming, or not generally solvable exactly by either simple method:

Problem	Classification
Fractional knapsack	?
0/1 knapsack	?
Interval scheduling	?
Weighted interval scheduling	?
Coin change with arbitrary coins	?
Minimum spanning tree	?
Traveling salesman	?

For each, give one sentence explaining the classification.

Exercise 20: Design Your Own Greedy Rule

Choose one of these domains:

• Scheduling
• Resource allocation
• String construction
• Graph optimization
• Compression

Define:

1. Input model
2. Objective
3. Greedy rule
4. Data structure
5. Correctness argument or counterexample

The exercise is complete only when you either prove the greedy rule or produce a counterexample.

Reference Answers

Use these only after attempting the exercises.

Exercise 1

Sort by finish time.

Selected:

[1,3], [3,5], [6,8]

or another compatible maximum set depending on endpoint convention.

Maximum count:

3

Exercise 3

Densities:

Item	Density
A	5
B	4
C	4
D	9

Order:

D, A, B, C

Take:

D fully
A fully
B fully
10/40 of C

Total:

90 + 100 + 120 + 40 = 350

Exercise 5

Profit order:

A, B, E, D, C

One optimal schedule:

Slot	Job
1	B
2	A
3	E

Total profit:

180

Exercise 6

Stops:

3

The car refuels at every station.

If the first station is moved from position 25 to position 26, the destination is unreachable.

Exercise 8

Merge order:

5 + 9 = 14
12 + 13 = 25
14 + 16 = 30
25 + 30 = 55
45 + 55 = 100

This is the classical Huffman construction.

Exercise 11

Sorted:

[1,2,2,3]

Boats:

3

The heaviest person 3 cannot pair with 1 because 3 + 1 > 3, so 3 must go alone.

Exercise 14

Sorted edges:

A-C(1), B-D(2), B-C(3), A-B(4), C-D(5)

Selected:

A-C, B-D, B-C

Total weight:

6

Takeaway

Exercises are where greedy reasoning becomes reliable. For each problem, identify the local rule, attack it with counterexamples, prove it with exchange or structural arguments, and then choose the simplest data structure that implements it efficiently. Greedy algorithms are short because their implementations are compact, not because their reasoning is trivial.