Regret Greedy (Undoable Greedy with Priority Queues): Scheduling with Deadlines & Stock Trading

1. When Pure Greedy Fails: Retroactive Replacement via Heaps

Consider the Variable-Length Course Scheduling Problem (Moore–Hodgson Algorithm, 1968 / Course Schedule III): Given $N$ courses, each with duration $t_i$ and deadline $d_i$, maximize the number of courses completed. Unlike Unit-Time Scheduling ($t_i = 1$), variable durations $t_i$ do not form a matroid! If we sort by deadline $d_1 \le d_2 \le \dots \le d_n$ and greedily take course $1$ ($t_1 = 100, d_1 = 100$), we might block courses $2$ and $3$ ($t_2 = 30, d_2 = 110$ and $t_3 = 30, d_3 = 120$).

2. Virtual Cancellation (Slope Trick / Stock Trading with Unlimited Transactions)

A second, deeper form of Regret Greedy is Virtual Undo (Equivalent to a 1-capacity Successive Shortest Path augmenting path or Slope Trick): Suppose on Day $i$ the stock price is $p_i$, and you want to pair Buy/Sell days to maximize profit (or match tasks to servers). If you buy at $p_1 = 10$, sell at $p_2 = 15$ (profit $+5$), and then see $p_3 = 22$, you regret selling at $15$ instead of $22$.

Observe the telescope identity:

When we match $p_2$ with $p_1$ to book profit $p_2 - p_1$, if we push $p_2$ back into the min-heap as a "virtual buy option", then later buying that virtual $p_2$ and selling at $p_3$ adds $p_3 - p_2$, which algebraically cancels the intermediate sale at $p_2$ and converts the trade into $(p_1, p_3)$!

3. Complexity Matrix

4. Reference C++20 Implementation

#include <algorithm>
#include <cstdint>
#include <functional>
#include <queue>
#include <vector>

struct Course {
    long long duration;
    long long deadline;
};

// 1. Moore-Hodgson Algorithm (Course Schedule III): Max courses completed before deadline
int max_courses_moore_hodgson(std::vector<Course> courses) {
    std::sort(courses.begin(), courses.end(), [](const Course& a, const Course& b) {
        return a.deadline < b.deadline;
    });

    std::priority_queue<long long> max_durations; // Max-heap of chosen course durations
    long long total_time = 0;

    for (const auto& c : courses) {
        total_time += c.duration;
        max_durations.push(c.duration);
        if (total_time > c.deadline) {
            // Regret Step: Evict the single longest course taken so far (might be c itself!)
            total_time -= max_durations.top();
            max_durations.pop();
        }
    }
    return static_cast<int>(max_durations.size());
}

// 2. Virtual Undo (Telescoping Heap): Buy/Sell at most 1 share per day, hold unlimited shares
long long max_profit_multi_share_trading(const std::vector<long long>& prices) {
    // Min-heap of available buy prices (both unused days and virtual undo options)
    std::priority_queue<long long, std::vector<long long>, std::greater<long long>> min_heap;
    long long total_profit = 0;

    for (long long p : prices) {
        if (!min_heap.empty() && min_heap.top() < p) {
            total_profit += (p - min_heap.top());
            min_heap.pop();
            // Push p TWICE:
            // 1st copy: allows cancelling the sale at p if a higher price p' > p appears later:
            //           (p - buy) + (p' - p) = p' - buy
            // 2nd copy: allows buying a brand new share on this day at price p
            min_heap.push(p);
        }
        min_heap.push(p);
    }
    return total_profit;
}