Practice Problems

Most greedy problems fall apart the moment you find the right ordering. The four problems below each exercise a different greedy rule. Before reading a solution, pick your rule and try to justify it in one sentence.

Problem 1. Choosing inspection times

Each sensor in a plant has a time window [l, r] (both ends inclusive) in which its reading must be checked. An inspector does a round at chosen moments and checks every sensor whose window contains that moment. Find the fewest rounds that check every sensor, and their times.

Approach: sort windows by end time. The earliest-ending unchecked window must be inspected by its end anyway, so placing the round as late as possible, at r, covers the most later windows. As an exchange argument: moving the first round of an optimal plan to r never uncovers a window.

def min_check_times(windows):
    times = []
    for l, r in sorted(windows, key=lambda w: w[1]):
        if not times or times[-1] < l:  # last round happened before this window
            times.append(r)
    return times


print(min_check_times([(1, 4), (2, 6), (5, 8), (7, 9), (10, 12)]))  # [4, 8, 12]

Problem 2. Loading spices (fractional knapsack)

A cart carries at most W kg. Each spice has a total value and weight, and you may scoop any portion of it. Find the maximum value you can load.

Approach: load spices in order of value per kilogram. When a spice is heavier than the remaining capacity, take just enough to fill the cart and stop. Swapping some expensive spice for a cheaper one can only lose value, so the rule is optimal. For exact results use fractions.Fraction, or compare ratios by cross-multiplication instead of division.

def max_cart_value(items, capacity):
    """items: list of (value, weight)."""
    total = 0.0
    for value, weight in sorted(items, key=lambda it: it[0] / it[1], reverse=True):
        if capacity <= 0:
            break
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
    return total


print(max_cart_value([(120, 3), (100, 5), (60, 4)], 10))  # 250.0

If items cannot be split (0/1 knapsack) this rule is wrong. With (60, 10), (100, 20), (120, 30) and capacity 50, ratio-greedy gets 160 while the optimum is 220.

Problem 3. Tasks finished before their deadlines

Each task has a duration and a deadline, and you process one task at a time without breaks, starting at time 0. Maximize the number of tasks finished on time (late tasks are simply not done).

Approach: accept tasks in order of deadline, and whenever the running time overshoots the current deadline, drop the longest task accepted so far. Dropping the longest keeps the count the same while freeing the most time for later tasks. You need a max-heap, so store negated durations in Python.