Proving Greedy Correctness: Greedy Stays Ahead & Exchange Arguments (Interval Scheduling, Minimizing Lateness)

1. Proof Paradigm I: "Greedy Stays Ahead" (Unweighted Interval Scheduling)

Given $n$ intervals $[s_i, f_i)$, select a maximum-size subset of mutually compatible intervals ($f_i \le s_j$ or $f_j \le s_i$). Plausible heuristics like Earliest Start Time, Shortest Duration ($f_i - s_i$), or Fewest Conflicts all fail on simple counterexamples. The unique simple rule that works is Earliest Finish Time (EFT): sort intervals by $f_1 \le f_2 \le \dots \le f_n$ and greedily pick the next compatible interval.

2. Proof Paradigm II: Adjacent Exchange Argument (Minimizing Maximum Lateness & Smith's Rule)

When every item must be scheduled (a permutation problem), we use a Local Exchange Argument:

• Minimizing Maximum Lateness ($L_{\max} = \max_i \max(0, C_i - d_i)$): Each job $i$ has processing time $t_i > 0$ and deadline $d_i$. Earliest Deadline First (EDF) sorts jobs by $d_1 \le d_2 \le \dots \le d_n$. Suppose an optimal schedule $O^*$ has an inversion ($d_i > d_j$, yet $i$ is scheduled immediately before $j$). Swapping adjacent jobs $i$ and $j$ leaves all other jobs unchanged, moves $j$ earlier (reducing $L_j$), and finishes $i$ at $j$'s old completion time $C'_i = C_j$. Since $d_i > d_j$, the new lateness $C_j - d_i < C_j - d_j \le L_{\max}(O^*)$. Thus swapping adjacent inversions never increases $L_{\max}$!
• Weighted Completion Time ($\sum_i w_i C_i$, Smith's Rule): Sort jobs by $w_i / t_i$ descending (i.e., $w_i t_j > w_j t_i$). Swapping an adjacent pair $(i, j)$ changes the total objective by $\Delta = w_i t_j - w_j t_i$, so an optimal schedule cannot contain any adjacent pair with $w_i / t_i < w_j / t_j$.

3. Complexity Matrix

4. Reference C++20 Implementation

#include <algorithm>
#include <cstdint>
#include <vector>

struct Interval {
    long long start;
    long long finish;
};

// 1. Maximum Disjoint Intervals via Earliest Finish Time (Greedy Stays Ahead)
int max_disjoint_intervals(std::vector<Interval> intervals) {
    if (intervals.empty()) return 0;
    std::sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return a.finish < b.finish;
    });

    int count = 1;
    long long last_finish = intervals[0].finish;
    for (std::size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i].start >= last_finish) {
            ++count;
            last_finish = intervals[i].finish;
        }
    }
    return count;
}

struct Job {
    long long processing_time;
    long long deadline;
    long long weight;
};

// 2. Minimize Maximum Lateness via Earliest Deadline First (Exchange Argument)
long long minimize_max_lateness(std::vector<Job> jobs) {
    std::sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        return a.deadline < b.deadline;
    });
    long long current_time = 0;
    long long max_lateness = 0;
    for (const auto& job : jobs) {
        current_time += job.processing_time;
        max_lateness = std::max(max_lateness, current_time - job.deadline);
    }
    return max_lateness;
}

// 3. Minimize Weighted Sum of Completion Times via Smith's Rule (w_i / t_i descending)
long long minimize_weighted_completion_time(std::vector<Job> jobs) {
    std::sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
        return static_cast<__int128>(a.weight) * b.processing_time >
               static_cast<__int128>(b.weight) * a.processing_time;
    });
    long long current_time = 0;
    long long total_weighted_cost = 0;
    for (const auto& job : jobs) {
        current_time += job.processing_time;
        total_weighted_cost += job.weight * current_time;
    }
    return total_weighted_cost;
}