DSA Part 16: Greedy Proofs & Scheduling

1. Problem and Motivation

A greedy algorithm makes one irrevocable, locally best choice after another and never reconsiders. That is either a huge win or a silent bug, depending on whether the problem actually has the structure that makes local choices safe. "It worked on my test cases" is not a proof. Without a correctness argument, a greedy algorithm is just an unverified heuristic that happens to look like an algorithm.

This lesson is about closing that gap. It introduces the exchange argument, the standard technique for proving a greedy strategy optimal, and applies it rigorously to a classic case (activity selection). It then works through three more greedy scheduling problems — jump game, interval scheduling, and job sequencing with deadlines and profits — so the proof habit has real problems to attach to, not just one worked example.

2. Prerequisites

Greedy algorithms are usually introduced as "the fast alternative to DP when you can get away with it." Before this lesson, you should already be comfortable with the DP side of that sentence: defining states, writing transitions, and reasoning about optimal substructure directly, without shortcuts. See Part 15: Core DP Patterns for that foundation.

The reason to sequence the lessons this way is that greedy is best understood as a special case: it is what happens when a DP's transition collapses to "always take the same one choice," and that collapse can be proven safe. If you cannot yet write the DP for a problem, you are not in a position to judge whether skipping it with greedy is justified — you are just guessing.

3. Greedy vs DP: How to Decide

Greedy algorithms make locally optimal choices at each step, hoping to find a global optimum. They work when the problem has the greedy-choice property (a local optimum leads to a global optimum) and optimal substructure (an optimal solution contains optimal solutions to subproblems). Unlike DP which considers all possibilities, greedy commits to a choice without looking back — making it faster ($O(n \log n)$ typical) but applicable to fewer problems.

The word doing all the work in that box is "prove." The next section turns that word into an actual proof technique instead of a feeling.

4. Activity Selection & the Exchange Argument

Given a set of activities with start and end times, select the maximum number of non-overlapping activities. The greedy strategy is deceptively simple: sort by end time, then always pick the activity that finishes earliest and doesn't overlap with the last selected. This works because finishing early leaves the most room for future activities — a provably optimal greedy choice. Time: $O(n \log n)$ for sorting.

def activity_selection(activities):
    """
    Select maximum non-overlapping activities
    activities: list of (start, end) tuples
    Time: O(n log n), Space: O(1)
    """
    # Sort by end time
    activities = sorted(activities, key=lambda x: x[1])

    selected = [activities[0]]
    last_end = activities[0][1]

    for start, end in activities[1:]:
        if start >= last_end:  # Non-overlapping
            selected.append((start, end))
            last_end = end

    return selected

# Example
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
result = activity_selection(activities)
print(f"Activities: {len(activities)}")
print(f"Max selected: {len(result)}")
print(f"Selected: {result}")

// Activity Selection - Maximum non-overlapping activities
// Time: O(n log n), Space: O(1)
#include <vector>
#include <algorithm>

class ActivitySelection {
public:
    static std::vector<std::pair<int, int>> select(
            std::vector<std::pair<int, int>>& activities) {
        // Sort by end time
        std::sort(activities.begin(), activities.end(),
                  [](auto& a, auto& b) { return a.second < b.second; });

        std::vector<std::pair<int, int>> selected;
        selected.push_back(activities[0]);
        int lastEnd = activities[0].second;

        for (int i = 1; i < activities.size(); i++) {
            if (activities[i].first >= lastEnd) {
                selected.push_back(activities[i]);
                lastEnd = activities[i].second;
            }
        }
        return selected;
    }
};

// Activity Selection - Maximum non-overlapping activities
// Time: O(n log n), Space: O(1)
import java.util.*;

class ActivitySelection {
    public static List<int[]> select(int[][] activities) {
        // Sort by end time
        Arrays.sort(activities, (a, b) -> a[1] - b[1]);

        List<int[]> selected = new ArrayList<>();
        selected.add(activities[0]);
        int lastEnd = activities[0][1];

        for (int i = 1; i < activities.length; i++) {
            if (activities[i][0] >= lastEnd) {
                selected.add(activities[i]);
                lastEnd = activities[i][1];
            }
        }
        return selected;
    }
}

Proving Greedy Correctness: The Exchange Argument

The exchange argument is the standard way to prove a greedy strategy is optimal. It has three moving parts:

1. Assume the worst case. Take any optimal solution OPT. If OPT already agrees with the greedy choice at every step, greedy is optimal and there is nothing to prove. So assume OPT differs from greedy's choice at some point — pick the earliest such point.
2. Exchange without loss. At that point, show you can swap OPT's choice for greedy's choice and get a new solution OPT' that is still feasible (obeys every constraint) and no worse than OPT (same or better objective value).
3. Induct to the end. Repeat the exchange at each remaining point of disagreement. Each exchange produces a solution that is still optimal (never worse than the previous one) and one step closer to matching greedy exactly. After finitely many exchanges, the solution equals greedy's output, and it is still optimal. Therefore greedy is optimal.

The proof never claims greedy's solution is the only optimal solution — only that it is an optimal one. It works by showing greedy's choices are always "safe," in the sense that no optimal solution is ever forced to avoid them.

Applied formally to activity selection: let the activities be sorted by finish time, $f(a_1) \le f(a_2) \le \dots \le f(a_n)$, so the greedy algorithm always selects $a_1$ first, then the earliest-finishing activity compatible with $a_1$, and so on. Let $G$ denote the set greedy selects.

Claim: $G$ has the maximum possible size among all sets of mutually non-overlapping activities.

Proof. Let OPT be any optimal (maximum-size) set of mutually compatible activities, and let $o_1$ be the activity in OPT with the earliest finish time.

• Step 1 — the exchange is safe. Since $a_1$ has the earliest finish time of all activities (not just OPT's), $f(a_1) \le f(o_1)$. Every other activity in OPT starts at or after $f(o_1)$ (otherwise it would overlap $o_1$, contradicting OPT's feasibility), so it also starts at or after $f(a_1)$. Therefore replacing $o_1$ with $a_1$ — forming $\text{OPT}' = \text{OPT} - \{o_1\} + \{a_1\}$ — keeps every remaining activity compatible with the new first activity. $\text{OPT}'$ is feasible and $|\text{OPT}'| = |\text{OPT}|$: the exchange lost nothing.
• Step 2 — reduce to a subproblem. Every activity remaining in $\text{OPT}'$ other than $a_1$ starts at or after $f(a_1)$, which is exactly the set of activities greedy considers eligible for its second pick. So $\text{OPT}' - \{a_1\}$ is an optimal solution to the smaller subproblem "select the maximum non-overlapping activities among those compatible with $a_1$" — the same subproblem greedy now faces.
• Step 3 — induct. By induction on the number of remaining activities, the same exchange can be applied at every subsequent step: at each point, OPT's earliest-finishing remaining activity can be swapped for greedy's next pick without shrinking the solution. Repeating this for all $n$ picks produces a solution identical to $G$, and every exchange preserved cardinality, so $|G| = |\text{OPT}'| = |\text{OPT}|$.

Since OPT was assumed optimal and $|G| = |\text{OPT}|$, $G$ is also optimal. $\blacksquare$

Notice the shape of this argument: it never argues greedy is optimal by exhaustively comparing it to every alternative. It argues that whatever the optimal solution looks like, it can always be reshaped — one safe exchange at a time — into exactly what greedy would have produced, without ever losing value. That reshaping argument is the exchange argument, and it is the template to reach for whenever you claim a greedy strategy is correct.

Staying Ahead: A Second Proof Technique

The exchange argument above proves greedy correct indirectly: it takes an assumed-optimal solution and reshapes it, one safe swap at a time, until it matches greedy exactly. Staying ahead is a different route to the same kind of conclusion. Instead of transforming some other solution into greedy's, it directly compares greedy's partial progress to any other algorithm's partial progress at every step, and shows greedy is never behind. If greedy's partial solution is always at least as good as any competitor's partial solution after each of the first $k$ steps, then by induction it is still at least as good after the final step — so greedy's finished solution is at least as good as any other finished solution, optimal ones included.

The two techniques prove the same kind of claim (greedy is optimal) but the object under the microscope differs: the exchange argument inspects a single, fixed, assumed-optimal solution and edits it; staying ahead inspects a running comparison between greedy and an arbitrary competitor, step by step, and never edits anything.

Worked Proof: Earliest Deadline First Minimizes Maximum Lateness

Single machine, $n$ jobs all available at time 0, no preemption once a job starts. Job $i$ needs $p_i$ time units and has a deadline $d_i$. Every job must be scheduled — unlike the Job Sequencing problem below, no job may be skipped. If a job finishes at time $C_i$, its lateness is $L_i = C_i - d_i$ (negative if it finishes early). The goal is to minimize the maximum lateness over all jobs. Earliest Deadline First (EDF) schedules jobs back-to-back in order of non-decreasing deadline: relabel the jobs so $d_1 \le d_2 \le \dots \le d_n$, and EDF runs $1, 2, \dots, n$ in that order with no idle time.

Proof, by induction on $k$.

• Base case ($k = 1$). Job 1 alone needs $p_1$ time units of machine time to finish, regardless of what schedule it appears in. The earliest it can possibly complete is $p_1 = T_1$ (run first, with no idle time before it); any other placement only delays it further. So in any schedule $S$, job 1's completion time is $\ge T_1$.
• Inductive step. Assume that in any schedule $S$, the latest completion time among jobs $\{1, \dots, k-1\}$ is $\ge T_{k-1}$. Now bring job $k$ into the picture. Finishing all of $\{1, \dots, k\}$ requires $p_1 + \dots + p_k = T_{k-1} + p_k$ total units of machine-busy time spent on just these $k$ jobs — that total cannot shrink no matter how the machine interleaves other jobs or idle time among them, because it is simply the sum of their processing times, and a single machine can only work on one job at a time. So the latest completion time among $\{1, \dots, k\}$ in $S$ is $\ge T_{k-1} + p_k = T_k$. This holds for every schedule $S$, so the invariant carries from $k-1$ to $k$.

By induction, the invariant holds for every $k$ from $1$ to $n$. Now use it: under EDF, job $k$ literally is the last of $\{1, \dots, k\}$ to finish (they run in order $1, \dots, k$), so its lateness is exactly $T_k - d_k$. Under any other schedule $S$, some job among $\{1, \dots, k\}$ finishes at or after $T_k$ (the invariant), and every job in that set has deadline $\le d_k$, so that job's lateness under $S$ is at least $T_k - d_k$ too. That makes $T_k - d_k$ a lower bound on $S$'s maximum lateness, for every $k$. Taking the largest such bound over all $k$:

for every valid schedule $S$. So no schedule can beat EDF's maximum lateness — EDF is optimal. $\blacksquare$

Notice the shape of this proof: nothing was swapped or reshaped. It built up a lower bound step by step ($T_1 - d_1$, then $T_2 - d_2$, and so on) that EDF hits exactly at every step and that every other schedule is provably stuck matching or missing. That running, step-by-step domination is the "staying ahead" pattern — greedy's partial solution never falls behind any competitor's, so by induction its final solution never falls behind either.

flowchart TD
    A["Step 1: T1 = p1
EDF's job 1 finishes at T1;
any schedule's job 1 finishes ≥ T1"] --> B["Step 2: T2 = p1 + p2
EDF still meets the bound;
any schedule's slowest of {1,2} finishes ≥ T2"]
    B --> C["..."]
    C --> D["Step k: Tk = p1 + ... + pk
Greedy (EDF) lateness = Tk − dk;
Any-Algorithm's worst job among first k is ≥ Tk − dk too"]
    D --> E["..."]
    E --> F["Step n: all n jobs scheduled"]
    F --> G["Conclusion by induction:
max lateness(EDF) ≤ max lateness(Any Algorithm)"]
                

Jobs A (p=2, d=2), C (p=3, d=3), B (p=1, d=4). EDF's order (A, C, B) caps maximum lateness at 2; the order (B, A, C) — still a valid schedule of the same three jobs — lets C miss its deadline by 3.

5. Jump Game

Given an array where each element represents the maximum jump length from that position, determine (a) if you can reach the last index, and (b) the minimum number of jumps. The greedy insight: maintain the farthest reachable index as you scan left-to-right. If your current position ever exceeds the farthest reach, you're stuck. For minimum jumps, use a "BFS-like" greedy: track the current reachable range (a "level"), and when you exhaust it, jump to the new farthest point.

def can_jump(nums):
    """
    LeetCode 55: Jump Game
    Can you reach the last index?
    Time: O(n), Space: O(1)
    """
    max_reach = 0

    for i, jump in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + jump)

    return True

def min_jumps(nums):
    """
    LeetCode 45: Jump Game II
    Minimum jumps to reach end
    Time: O(n), Space: O(1)
    """
    if len(nums) <= 1:
        return 0

    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            jumps += 1
            current_end = farthest

            if current_end >= len(nums) - 1:
                break

    return jumps

# Examples
nums1 = [2, 3, 1, 1, 4]
print(f"Array: {nums1}")
print(f"Can reach end: {can_jump(nums1)}")  # True
print(f"Min jumps: {min_jumps(nums1)}")  # 2

nums2 = [3, 2, 1, 0, 4]
print(f"\nArray: {nums2}")
print(f"Can reach end: {can_jump(nums2)}")  # False

// LeetCode 55: Jump Game & LeetCode 45: Jump Game II
#include <vector>
#include <algorithm>

class JumpGame {
public:
    // Can reach the last index?
    static bool canJump(std::vector<int>& nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > maxReach) return false;
            maxReach = std::max(maxReach, i + nums[i]);
        }
        return true;
    }

    // Minimum jumps to reach end
    static int minJumps(std::vector<int>& nums) {
        if (nums.size() <= 1) return 0;

        int jumps = 0, currentEnd = 0, farthest = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            farthest = std::max(farthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                if (currentEnd >= nums.size() - 1) break;
            }
        }
        return jumps;
    }
};

// LeetCode 55: Jump Game & LeetCode 45: Jump Game II

class JumpGame {
    // Can reach the last index?
    public static boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) return false;
            maxReach = Math.max(maxReach, i + nums[i]);
        }
        return true;
    }

    // Minimum jumps to reach end
    public static int minJumps(int[] nums) {
        if (nums.length <= 1) return 0;

        int jumps = 0, currentEnd = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                if (currentEnd >= nums.length - 1) break;
            }
        }
        return jumps;
    }
}

6. Interval Scheduling

A family of problems involving overlapping intervals: merge overlapping intervals, find minimum meeting rooms, or insert a new interval. The common preprocessing step is sorting by start time (or end time, depending on the variant). For merging: sort by start, then extend the current interval's end if the next overlaps; otherwise close and start a new interval. For meeting rooms: count the maximum overlap at any point (equivalent to a sweep line or min-heap approach).

def erase_overlap_intervals(intervals):
    """
    LeetCode 435: Non-overlapping Intervals
    Minimum intervals to remove for no overlap
    Time: O(n log n), Space: O(1)
    """
    if not intervals:
        return 0

    # Sort by end time
    intervals.sort(key=lambda x: x[1])

    removals = 0
    prev_end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] < prev_end:  # Overlap
            removals += 1
        else:
            prev_end = intervals[i][1]

    return removals

def merge_intervals(intervals):
    """
    LeetCode 56: Merge Intervals
    Time: O(n log n), Space: O(n)
    """
    if not intervals:
        return []

    # Sort by start time
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:  # Overlap
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

# Examples
intervals1 = [[1, 2], [2, 3], [3, 4], [1, 3]]
print(f"Intervals: {intervals1}")
print(f"Remove to eliminate overlap: {erase_overlap_intervals(intervals1)}")  # 1

intervals2 = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(f"\nIntervals: {intervals2}")
print(f"Merged: {merge_intervals(intervals2)}")  # [[1,6],[8,10],[15,18]]

// LeetCode 435: Non-overlapping Intervals
// LeetCode 56: Merge Intervals
#include <vector>
#include <algorithm>

class IntervalScheduling {
public:
    // Min removals for no overlap
    static int eraseOverlapIntervals(std::vector<std::vector<int>>& intervals) {
        if (intervals.empty()) return 0;

        std::sort(intervals.begin(), intervals.end(),
                  [](auto& a, auto& b) { return a[1] < b[1]; });

        int removals = 0, prevEnd = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < prevEnd)
                removals++;
            else
                prevEnd = intervals[i][1];
        }
        return removals;
    }

    // Merge overlapping intervals
    static std::vector<std::vector<int>> mergeIntervals(
            std::vector<std::vector<int>>& intervals) {
        if (intervals.empty()) return {};

        std::sort(intervals.begin(), intervals.end());
        std::vector<std::vector<int>> merged = {intervals[0]};

        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] <= merged.back()[1])
                merged.back()[1] = std::max(merged.back()[1], intervals[i][1]);
            else
                merged.push_back(intervals[i]);
        }
        return merged;
    }
};

// LeetCode 435: Non-overlapping Intervals
// LeetCode 56: Merge Intervals
import java.util.*;

class IntervalScheduling {
    // Min removals for no overlap
    public static int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int removals = 0, prevEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < prevEnd)
                removals++;
            else
                prevEnd = intervals[i][1];
        }
        return removals;
    }

    // Merge overlapping intervals
    public static int[][] mergeIntervals(int[][] intervals) {
        if (intervals.length == 0) return new int[][]{};

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] last = merged.get(merged.size() - 1);
            if (intervals[i][0] <= last[1])
                last[1] = Math.max(last[1], intervals[i][1]);
            else
                merged.add(intervals[i]);
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

7. Job Sequencing with Deadlines and Profits

Each job $i$ takes one unit of time, has a deadline $d_i$, and earns a profit $p_i$ if it completes at or before that deadline. At most one job can run in any unit time slot. Choose a subset of jobs and an assignment of jobs to slots that maximizes total profit.

The greedy strategy: sort jobs by profit in descending order, then for each job in that order, place it in the latest free slot at or before its deadline. If no such slot is free, skip the job. Scheduling as late as possible is the key move — it keeps every earlier slot open for jobs with tighter deadlines that haven't been considered yet, so a high-profit job never "steals" a slot that only a soon-to-expire job could have used. This is the same family of argument as activity selection's exchange proof: any optimal schedule can be reshaped, one job at a time in decreasing profit order, to place each job as late as greedy would, without losing profit.

def job_sequencing(jobs):
    """
    Job Sequencing with Deadlines and Profits
    jobs: list of (job_id, deadline, profit) tuples
    Time: O(n^2) after sorting, Space: O(n) for slots
    """
    # Sort jobs by profit, descending
    jobs = sorted(jobs, key=lambda x: x[2], reverse=True)

    max_deadline = max(job[1] for job in jobs)
    slots = [None] * (max_deadline + 1)  # slots[1..max_deadline] used, slot 0 unused

    total_profit = 0
    scheduled = []

    for job_id, deadline, profit in jobs:
        # Scan from the job's deadline down to slot 1 for a free slot
        for t in range(min(deadline, max_deadline), 0, -1):
            if slots[t] is None:
                slots[t] = job_id
                total_profit += profit
                scheduled.append((job_id, t))
                break

    return scheduled, total_profit

# Example
jobs = [("J1", 4, 20), ("J2", 1, 10), ("J3", 1, 40), ("J4", 1, 30), ("J5", 3, 50)]
scheduled, profit = job_sequencing(jobs)
print("Scheduled (job, slot):", scheduled)
print("Total profit:", profit)  # 110

// Job Sequencing with Deadlines and Profits
// Time: O(n^2) after sorting, Space: O(n) for slots
#include <vector>
#include <algorithm>
#include <string>
#include <utility>

struct Job {
    std::string id;
    int deadline;
    int profit;
};

class JobSequencing {
public:
    static std::pair<std::vector<std::pair<std::string, int>>, int> schedule(
            std::vector<Job> jobs) {
        // Sort jobs by profit, descending
        std::sort(jobs.begin(), jobs.end(),
                  [](const Job& a, const Job& b) { return a.profit > b.profit; });

        int maxDeadline = 0;
        for (auto& job : jobs) maxDeadline = std::max(maxDeadline, job.deadline);

        std::vector<bool> occupied(maxDeadline + 1, false);  // slot 0 unused
        std::vector<std::pair<std::string, int>> scheduled;
        int totalProfit = 0;

        for (auto& job : jobs) {
            int latest = std::min(job.deadline, maxDeadline);
            for (int t = latest; t >= 1; t--) {
                if (!occupied[t]) {
                    occupied[t] = true;
                    scheduled.push_back({job.id, t});
                    totalProfit += job.profit;
                    break;
                }
            }
        }
        return {scheduled, totalProfit};
    }
};

// Job Sequencing with Deadlines and Profits
// Time: O(n^2) after sorting, Space: O(n) for slots
import java.util.*;

class JobSequencing {
    static class Job {
        String id;
        int deadline;
        int profit;
        Job(String id, int deadline, int profit) {
            this.id = id;
            this.deadline = deadline;
            this.profit = profit;
        }
    }

    public static int schedule(List<Job> jobs, List<String> scheduledOut) {
        jobs.sort((a, b) -> b.profit - a.profit);

        int maxDeadline = 0;
        for (Job job : jobs) maxDeadline = Math.max(maxDeadline, job.deadline);

        boolean[] occupied = new boolean[maxDeadline + 1];  // slot 0 unused

        int totalProfit = 0;
        for (Job job : jobs) {
            int latest = Math.min(job.deadline, maxDeadline);
            for (int t = latest; t >= 1; t--) {
                if (!occupied[t]) {
                    occupied[t] = true;
                    scheduledOut.add(job.id + "@slot" + t);
                    totalProfit += job.profit;
                    break;
                }
            }
        }
        return totalProfit;
    }

    public static void main(String[] args) {
        List<Job> jobs = new ArrayList<>(List.of(
            new Job("J1", 4, 20),
            new Job("J2", 1, 10),
            new Job("J3", 1, 40),
            new Job("J4", 1, 30),
            new Job("J5", 3, 50)
        ));
        List<String> scheduled = new ArrayList<>();
        int profit = schedule(jobs, scheduled);
        System.out.println("Scheduled: " + scheduled);
        System.out.println("Total profit: " + profit);  // 110
    }
}

8. Exercises and Mastery

Easy

1. Assign Cookies (LeetCode 455): each child has a greed factor and each cookie has a size; a child is content only with a cookie of size at least their greed factor. Sort both arrays, then use two pointers to match the smallest cookie that satisfies the least-greedy unsatisfied child. Count the maximum number of content children.
2. State, in your own words, why sorting both arrays first is what makes the two-pointer scan a valid greedy — what would go wrong if either array were left unsorted?

Medium

1. Jump Game II: re-derive min_jumps from the Jump Game section above without looking at the code, then write a short exchange-argument-style justification for why expanding to the farthest point reachable within the current "level" before incrementing the jump count never produces more jumps than any other reachable-set strategy.
2. Adapt the interval scheduling "minimum removals" code to instead report the minimum number of meeting rooms needed to host all given intervals.

Hard

1. Job sequencing with variable durations: suppose each job also has a duration $t_i > 1$, not just a deadline, still occupying a contiguous block of unit slots. Does "sort by profit, place as late as possible" still work? Construct a small counterexample: two jobs with the same deadline where a long, moderately profitable job blocks two short, more profitable jobs combined. In general, this variant is closely related to single-machine scheduling problems that are NP-hard once duration and profit both vary — greedy alone is no longer sufficient, and you need DP or a scheduling heuristic with a proven approximation bound instead. Sketch (pseudocode is fine) how the slot array from the unit-duration version would need to become a per-duration interval-occupancy check, and note where that sketch stops being efficient.

Review rhythm: tomorrow, reproduce the exchange-argument proof for activity selection without notes; next week, implement job sequencing in all three languages from the problem statement alone; several weeks later, apply the same three-step exchange-argument template (assume disagreement, exchange without loss, induct) to a new greedy claim you haven't seen before. Finally, teach the difference between "a greedy algorithm that happens to pass the sample tests" and "a greedy algorithm with a proof" to someone who has only seen DP.

9. Summary Cheat Sheet

• Greedy is safe only when the greedy-choice property and optimal substructure both hold — and "safe" needs a proof, not a passing test suite.
• The exchange argument proves greedy optimal in three steps: assume an optimal solution disagrees with greedy at some point, show the disagreement can be exchanged away without loss, then induct until the solutions match.
• Activity selection: sort by finish time, always take the earliest-finishing compatible activity; proven optimal because no optimal solution's first pick can finish earlier than greedy's.
• Jump Game: track the farthest reachable index; Jump Game II expands the current reachable "level" before incrementing the jump count.
• Interval scheduling: sort by end time to minimize removals, or by start time to merge; both reduce to the same one-pass sweep after sorting.
• Job sequencing with deadlines and profits: sort by profit descending, place each job in the latest free slot at or before its deadline; an $O(n \log n)$ DSU-based slot finder exists but the $O(n^2)$ scan is enough to see the proof.
• Variable job durations break the simple slot-scan greedy — that variant edges into NP-hard scheduling territory and needs DP or an approximation algorithm instead.