Greedy

Quick Revisit

• USE WHEN: Building a solution piece-by-piece where the locally optimal choice is globally optimal
• INVARIANT: After each greedy step, the partial solution is a subset of some optimal solution (exchange argument)
• TIME: O(n log n) typical (sort + scan) | SPACE: O(n)
• CLASSIC BUG: Assuming greedy works without verifying the exchange argument—leads to WA on tricky cases
• PRACTICE: Practice Ladder

The greedy paradigm: build a solution piece by piece, always picking the locally optimal choice and never looking back. When the greedy-choice property holds, this produces a globally optimal solution with almost no overhead—sort once, scan once, done.

Difficulty: Intermediate | Prerequisites: Sorting and Searching, Binary Search | CF Rating Range: 1000–1800 | Contest Frequency: Common

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• The Exchange Argument—Proving Your Greedy is Correct
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading
• Rating Progression
• Before You Code Checklist
• What Would You Do If...?
• The Mistake That Teaches
• Debug This
• Code Reading Exercise
• What to Solve Next
• Solve With Me—CF 1325D

---

Intuition

You have 6 activities, each with a start and end time:

  Activity   Start   End
  --------   -----   ---
  A            0      3
  B            1      4
  C            2      5
  D            4      7
  E            6      9
  F            8     11

Goal: pick the maximum number of non-overlapping activities.

Naive approach: enumerate every subset of activities, check for overlaps, keep the largest valid set. With $n=6$ activities that is $2^6=64$ subsets. For $n=30$ it is $2^{30}\approx {10}^9$—already too slow. For the typical contest constraint $n\le 2\times {10}^5$, brute force is hopeless.

Brute force is a dead end. We need a rule that commits to one choice at a time, left to right, without revisiting.

Always pick the activity that finishes earliest among those compatible with your current selection—this leaves the maximum room for future activities.

Think of it like parking cars bumper-to-bumper: if every car is as short as possible, you fit the most. The key insight is that finishing early is strictly better than finishing late—it never costs you anything and always leaves more room.

This "earliest end time" rule is the greedy choice. It is local (considers only the next best activity) yet produces a global optimum. The strategy breaks when the problem lacks the greedy-choice property—for instance, 0/1 knapsack, where taking the locally best item can block a superior combination.

Checkpoint: Why does sorting by start time (earliest start first) fail for interval scheduling maximization, while sorting by end time works?

Think first, then click

A job that starts earliest might span a very long time, blocking many short jobs. Sorting by end time guarantees each picked activity frees the timeline as early as possible, leaving maximum room for future picks. The exchange argument proves: swapping any optimal choice for the earlier-ending greedy choice never reduces the count.

Visual Walkthrough

Sort the 6 activities by end time, then greedily select:

  Timeline: 0   1   2   3   4   5   6   7   8   9  10  11
            |---|---|---|---|---|---|---|---|---|---|---|---|

  Sorted by end time:
  A: [--------)       end=3
  B:   [--------)     end=4
  C:     [--------)   end=5
  D:           [--------)   end=7
  E:               [--------)   end=9
  F:                     [--------)   end=11

  Step 1: last_end = -inf.  A starts at 0 >= -inf.  PICK A.  last_end = 3.
  Step 2: B starts at 1 < 3.   SKIP (overlaps A).
  Step 3: C starts at 2 < 3.   SKIP (overlaps A).
  Step 4: D starts at 4 >= 3.  PICK D.  last_end = 7.
  Step 5: E starts at 6 < 7.   SKIP (overlaps D).
  Step 6: F starts at 8 >= 7.  PICK F.  last_end = 11.

  Selected: {A, D, F} -- 3 activities   (6 comparisons, done)

  0   1   2   3   4   5   6   7   8   9  10  11
  |---|---|---|---|---|---|---|---|---|---|---|---|
  [A-------)   [D-----------)   [F-----------)

Total work: $O(n\log n)$ for the sort, $O(n)$ for the scan. Compared to $O(2^n)$, an astronomical speedup.

The Invariant

Invariant (exchange argument): After each greedy step, the set of chosen activities is a subset of some optimal solution.

Exchange argument—interval scheduling proof:

1. Let $G=\{g_1,g_2,\dots ,g_k\}$ be the greedy solution (sorted by end time).
2. Let $O=\{o_1,o_2,\dots ,o_m\}$ be an optimal solution with $m\ge k$, also sorted by end time.
3. Claim: $\text{end}(g_i)\le \text{end}(o_i)$ for every $i$.
4. Proof by induction. Base: $g_1$ has the earliest end time of all activities, so $\text{end}(g_1)\le \text{end}(o_1)$.
5. Inductive step: assume $\text{end}(g_{i-1})\le \text{end}(o_{i-1})$. Then every activity compatible with $o_{i-1}$ is also compatible with $g_{i-1}$. Greedy picks the compatible activity with the earliest end time, so $\text{end}(g_i)\le \text{end}(o_i)$.
6. Since each greedy choice finishes no later than the corresponding optimal choice, greedy selects at least as many activities: $k\ge m$. Combined with $m\ge k$ (optimality of $O$), we get $k=m$.

Generalized exchange argument template (works beyond interval scheduling):

  +------------------------------------------------------------------+
  | EXCHANGE ARGUMENT TEMPLATE                                       |
  |                                                                  |
  | 1. Let G be the greedy solution and O be any optimal solution.   |
  | 2. Find the first position i where G and O differ:               |
  |    G chooses element g, O chooses element o (g != o).            |
  | 3. Construct O' by swapping o for g in O.                        |
  | 4. Show that O' is still feasible (satisfies all constraints).   |
  | 5. Show that cost(O') <= cost(O)  (O' is no worse).             |
  |    This is the KEY step: argue from the greedy criterion         |
  |    why g is at least as good as o in this position.              |
  | 6. Repeat: O' agrees with G on one more position.               |
  |    After finitely many swaps, O becomes G with no loss.          |
  |    Therefore G is optimal.                                       |
  +------------------------------------------------------------------+

Step 5 is where the problem-specific reasoning lives. For interval scheduling: $\text{end}(g)\le \text{end}(o)$, so replacing $o$ with $g$ leaves at least as much room for future picks. For weighted job scheduling (minimize weighted completion time): swapping two adjacent jobs $i,j$ with $p_i/w_i<p_j/w_j$ reduces the total weighted cost because $w_j\cdot p_i<w_i\cdot p_j$.

More Exchange Argument Examples

The exchange argument is the backbone of every greedy proof. The same four-step template works across radically different problem types—the only thing that changes is the algebra in step 3. Three more worked examples make this concrete.

Example A: Job Scheduling with Deadlines (Minimizing Lateness)

Problem: $n$ jobs, each with processing time $p_i$ and deadline $d_i$. All jobs must run on a single machine (no preemption). Minimize the maximum lateness $L_{max}=\underset{i}{max}(C_i-d_i)$, where $C_i$ is the completion time of job $i$.

Greedy rule: Sort jobs by deadline $d_i$ ascending (Earliest Deadline First—EDF).

Exchange argument proof:

1. Let $G$ be the EDF schedule. Suppose some optimal schedule $O$ has an inversion: two adjacent jobs $i,j$ where $j$ is scheduled before $i$ but $d_j>d_i$.
2. Construct $O^{\prime }$ by swapping $i$ and $j$ in $O$. All other jobs are unaffected.
3. Feasibility: Both $i$ and $j$ still run; the total processing time is unchanged. The swap does not affect any other job's completion time.
4. Cost analysis: Let $t$ be the start time of the earlier job. Before the swap: $C_j=t+p_j$, $C_i=t+p_j+p_i$. After the swap: $C_i^{\prime }=t+p_i$, $C_j^{\prime }=t+p_i+p_j$.
   • Job $j$'s completion time rises from $t+p_j$ to $t+p_i+p_j$, and job $i$'s drops from $t+p_j+p_i$ to $t+p_i$.
   • The new lateness of $j$ is $C_j^{\prime }-d_j=t+p_i+p_j-d_j$. The old lateness of $i$ was $C_i-d_i=t+p_j+p_i-d_i$. Since $d_i\le d_j$, we have $C_j^{\prime }-d_j\le C_i-d_i$, so the swap does not increase $L_{max}$.
5. Each swap removes one inversion. After finitely many swaps $O$ becomes EDF with $L_{max}$ no worse. Therefore EDF is optimal. $◻$

Example B: Coin Change—Where Greedy Fails

Problem: Make change for amount $T$ using denominations $\{1,3,4\}$, minimizing the number of coins.

Greedy rule (largest-coin-first): Always pick the largest denomination $\le$ remaining amount.

Greedy attempt for $T=6$:

  Remaining = 6.  Largest <= 6 is 4.  Take 4.  Remaining = 2.
  Remaining = 2.  Largest <= 2 is 1.  Take 1.  Remaining = 1.
  Remaining = 1.  Largest <= 1 is 1.  Take 1.  Remaining = 0.
  Greedy answer: 4 + 1 + 1 = 3 coins.

Optimal: $3+3=2$ coins.

Why the exchange argument breaks: Try step 5 of the template. Suppose optimal uses coin $o=3$ at some position and greedy wants $g=4$. Replacing $o$ with $g$ overshoots (we took 4 instead of 3, increasing the used amount by 1, forcing an extra coin later to compensate). The swap is not cost-neutral—it increases total coins. The greedy criterion (take the biggest) is not safe because the non-divisibility of denominations means overshooting one step creates a deficit that costs more to fix later.

Lesson: When you try to write the exchange argument and step 5 fails—the swap makes things worse—this is a concrete signal the problem needs DP. For coin change with arbitrary denominations, the correct approach is $O(T\cdot |\text{denominations}|)$ DP.

Example C: Minimizing Total Weighted Completion Time

Problem: $n$ jobs on a single machine, job $i$ has processing time $p_i$ and weight $w_i$. Schedule all jobs to minimize $\sum _i{w}_i\cdot C_i$ where $C_i$ is the completion time of job $i$.

Greedy rule: Sort by $p_i/w_i$ ascending (equivalently, $w_i/p_i$ descending—prioritize short, heavy jobs).

Exchange argument proof (adjacent swap):

1. Suppose adjacent jobs $i,j$ are scheduled with $i$ before $j$. Let $T$ be the time before both start.
2. $i$-then-$j$ cost contribution: $w_i(T+p_i)+w_j(T+p_i+p_j)$.
3. $j$-then-$i$ cost contribution: $w_j(T+p_j)+w_i(T+p_j+p_i)$.
4. Subtract: ($i$-first) $-$ ($j$-first) $=w_j\cdot p_i-w_i\cdot p_j$.
5. $i$-before-$j$ is better $⟺w_j\cdot p_i<w_i\cdot p_j⟺p_i/w_i<p_j/w_j$.
6. If any adjacent pair violates this order, swapping them strictly improves the objective. An optimal schedule has no such violations, so it is sorted by $p_i/w_i$. Therefore the greedy (sorted) schedule is optimal. $◻$

This is the Smith's Rule proof and is one of the cleanest examples of an adjacent-swap exchange argument. Note how the algebra directly produces the sorting key.

Greedy Proof Template (Contest Fill-in-the-Blank)

In a contest, you rarely write a formal proof—but you must convince yourself the greedy works before coding. Use this fill-in-the-blank template mentally (or on scratch paper):

  +------------------------------------------------------------------+
  | GREEDY PROOF TEMPLATE -- CONTEST VERSION                         |
  +------------------------------------------------------------------+
  |                                                                  |
  | PROBLEM: ____________________________________________            |
  |                                                                  |
  | GREEDY RULE: Sort by ______________ and then ______________.     |
  |                                                                  |
  | EXCHANGE ARGUMENT:                                               |
  |                                                                  |
  | 1. ASSUME: An optimal solution O differs from greedy G at        |
  |    position i. O uses element [o] and G uses element [g].        |
  |                                                                  |
  | 2. SWAP: Replace [o] with [g] in O to get O'.                   |
  |                                                                  |
  | 3. FEASIBILITY: O' is still valid because ___________________    |
  |    _________________________________________________________.    |
  |                                                                  |
  | 4. COST: O' is no worse because __________________________       |
  |    _________________________________________________________.    |
  |    (This is where the sorting criterion matters:                 |
  |     because [g] was chosen by greedy, we know _____________      |
  |     _____________________ which implies cost(O') <= cost(O).)    |
  |                                                                  |
  | 5. CONCLUSION: Each swap makes O agree with G on one more        |
  |    position without worsening cost -> G is optimal.              |
  |                                                                  |
  | FILLED EXAMPLE (Interval Scheduling):                            |
  |   GREEDY RULE: Sort by end time ascending, pick earliest finish. |
  |   FEASIBILITY: g ends <= o ends, so all activities after o       |
  |     in O are still compatible with g.                            |
  |   COST: Same count -- we replaced one interval with one interval.|
  |   KEY PROPERTY: end(g) <= end(o) because greedy picks earliest.  |
  +------------------------------------------------------------------+

How to use in contest:

1. Write your greedy rule in one sentence.
2. Try to fill in the FEASIBILITY and COST blanks. If you can fill both in under 2 minutes, code the greedy.
3. If you get stuck at COST (you cannot explain why the swap is not worse), stop—the problem likely needs DP.

How to Identify a Greedy Problem / Discover the Sorting Key

1. Can you sort by some key? Look for a natural ordering—end times, deadlines, ratios, differences. If two elements $a$ and $b$ are adjacent, ask: "when is $a$-before-$b$ better than $b$-before-$a$?" The answer defines your comparator.
2. Can you prove the greedy choice is safe via exchange argument? Walk through the template above. If you cannot fill in step 5—if you cannot explain why the greedy choice is at least as good—the problem likely needs DP.
3. Does the problem have optimal substructure? After making the greedy choice, the remaining subproblem must have the same structure. If the greedy choice changes the subproblem in complex ways (e.g., 0/1 knapsack: taking an item changes remaining capacity and eliminates that item), greedy alone will not suffice.

Greedy vs DP Trade-Off

Both greedy and DP exploit optimal substructure, but greedy needs something more: the greedy-choice property—a locally optimal choice must also be part of a globally optimal solution. When that property holds, the gains are dramatic:

Aspect	Greedy	DP
Time	$O(n\log n)$ sort + $O(n)$ pass	$O(n\cdot S)$ where $S$ = state space
Space	$O(1)$ to $O(n)$	$O(S)$ (often $O(n\cdot W)$ or $O(n^2)$)
Implementation	Short, simple	Longer, more complex
Correctness	Requires exchange-argument proof	Correct by construction (recurrence)

Rule of thumb: try greedy first. If you can sketch the exchange argument in your head in under two minutes, code the greedy. If you can't—or if the problem forces you to track additional state like remaining capacity—switch to DP.

What the Code Won't Teach You

The sorting key IS the exchange argument, made concrete. When you compare two adjacent elements $i$ and $j$ in some ordering and show "i before j is at least as good as j before i," the condition $\text{cost}(i,j)\le \text{cost}(j,i)$ directly gives you the comparator. The comparator is the exchange argument. This is why deriving the comparator from the exchange argument is the correct approach, not guessing the sort key.

  Deriving the sort key from the exchange argument:

  Problem: minimize total weighted completion time
  Jobs: (p_i, w_i) = processing time and weight

  Compare two adjacent orderings:

  Order A: job i then job j          Order B: job j then job i
  +--------+--------+               +--------+--------+
  |  job i |  job j |               |  job j |  job i |
  +--------+--------+               +--------+--------+
  T     T+p_i    T+p_i+p_j         T     T+p_j    T+p_j+p_i

  Cost A: w_i*(T+p_i) + w_j*(T+p_i+p_j)
  Cost B: w_j*(T+p_j) + w_i*(T+p_j+p_i)

  A - B = w_j*p_i - w_i*p_j

  A is better when: w_j*p_i < w_i*p_j
                    p_i/w_i < p_j/w_j

  --> Sort key: ascending p_i/w_i
  --> Comparator: (long long)a.p * b.w < (long long)b.p * a.w

Greedy fails exactly when the problem has non-trivial state. Greedy commits without memory. If "which choice is best" depends on what you've already chosen—if the problem has state—greedy is flying blind. That is the formal reason 0/1 knapsack needs DP: taking item A shrinks the remaining capacity, which changes which items are worth taking next. The greedy has no way to account for this.

  Greedy has NO memory:           DP tracks STATE:

  Fractional knapsack:            0/1 knapsack:
  "Take best ratio item"          "Take item A or not?"
       |                               /            \
       v                         Take A            Skip A
  Remaining capacity              cap = W-w_A       cap = W
  doesn't matter --               DIFFERENT          SAME
  we can take a fraction          remaining items    remaining items
  of the next item too.           --> state matters  --> state matters

  Greedy works because            DP needed because
  fractions mean no               choices affect
  "wasted" capacity.              future options.

Knowing why greedy works is half the battle. The other half is recognizing which problems admit a greedy solution at all.

When to Reach for This

Trigger phrases in problem statements:

• "maximize the number of non-overlapping ..."
• "minimize the total cost / completion time / penalty"
• "schedule ... to minimize / maximize ..."
• "choose items ... greedily" (rare but explicit)
• "sort and select"

Counter-examples—problems that look greedy but need DP:

Problem	Why greedy fails	Correct approach
0/1 Knapsack	Taking the highest-ratio item can block a better combination	DP on capacity
Longest Increasing Subsequence	Greedily taking the smallest next element does not guarantee length; patient sorting works but is essentially DP	DP with binary search, $O(n\log n)$
Coin Change (arbitrary denominations)	Largest-coin-first fails for denominations like $\{1,3,4\}$ with target 6 (greedy: $4+1+1$; optimal: $3+3$)	DP on amount
Edit Distance	No local choice rule leads to a global optimum	DP on two strings

If you find yourself wanting to "undo" a greedy choice, or needing to track a second dimension of state, that is a strong signal you need DP—or at minimum, greedy with a regret/undo mechanism via priority queue.

Greedy vs DP Decision Tree

Choosing between greedy and DP is one of the most consequential decisions in competitive programming. The table below puts concrete problems side by side with the reasoning that separates them.

Problem	Greedy?	DP?	Distinguishing Feature
Activity Selection (max non-overlapping intervals)	Yes	Works but overkill	Greedy choice: always pick earliest finish. Exchange argument shows no interval the greedy skips could improve the count.
0/1 Knapsack (indivisible items, maximize value)	No	Yes	No greedy ordering works. Taking the best ratio item may waste capacity. Must track remaining capacity as a state dimension.
Fractional Knapsack (divisible items)	Yes	Overkill	Items are divisible—sort by value/weight ratio and pour. No capacity "waste" possible, so the greedy choice is always safe.
Coin Change (min coins, arbitrary denominations)	No	Yes	Greedy (largest-first) fails for non-canonical denomination sets (e.g., $\{1,3,4\}$, target 6). Must enumerate sub-amounts.
Huffman Coding (optimal prefix-free code)	Yes	Not natural	Merging the two cheapest nodes is provably optimal (exchange argument on tree structure). No DP state needed.
Weighted Job Scheduling (max weight, non-overlapping)	No	Yes	Unlike unweighted version, different weights mean you cannot just pick earliest finish—a long heavy job may beat two light ones. DP on sorted end times with binary search.
Minimum Spanning Tree (Kruskal's / Prim's)	Yes	Not applicable	Matroid structure guarantees greedy works. Adding the cheapest safe edge never creates a problem (cut property).
Longest Common Subsequence	No	Yes	No local choice rule works—matching character $i$ early might prevent a longer match later. Need 2D state on both string positions.
Minimize Maximum Lateness (single machine, deadlines)	Yes	Overkill	EDF (earliest deadline first)—adjacent swap argument shows inversions always increase max lateness.
Subset Sum (does a subset sum to $T$?)	No	Yes	Greedy (largest-first) can overshoot or undershoot. Must track reachable sums as DP states.

Decision heuristic—ask these questions in order:

  1. Can I sort by some key and make irrevocable choices?
     ├─ YES -> Try exchange argument (2 min mental check)
     │        ├─ Argument works -> GREEDY
     │        └─ Argument fails -> DP (or greedy + regret)
     └─ NO  -> Probably DP (or search / flow)

  2. Does the problem force me to track extra state?
     (remaining capacity, subset membership, two positions in two strings)
     ├─ YES -> DP
     └─ NO  -> Likely greedy

  3. Does the problem have a "divisibility" or "matroid" structure?
     (fractional items, matroid intersection, spanning trees)
     ├─ YES -> Greedy
     └─ NO  -> Investigate further

Checkpoint: You're solving a problem and your greedy approach gives the wrong answer on a small test case. How do you decide whether to fix the greedy strategy or switch to DP?

Think first, then click

Try the exchange argument: can you always swap an optimal solution's choice for your greedy choice without making it worse? If you can't construct this argument—or if you find a counterexample where undoing a greedy choice would help—the problem likely lacks the greedy-choice property and needs DP. Key signal: if you need to "undo" a choice or track a second state dimension (like remaining capacity), use DP.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
sort(first, last)	<algorithm>	Sort range ascending	$O(n\log n)$
sort(first, last, cmp)	<algorithm>	Sort with custom comparator	$O(n\log n)$
stable_sort(first, last, cmp)	<algorithm>	Stable sort (preserves equal-element order)	$O(n\log n)$
nth_element(first, nth, last)	<algorithm>	Partition so nth element is in sorted position	$O(n)$ average
partial_sort(first, mid, last)	<algorithm>	Sort only first mid - first elements	$O(n\log k)$
max_element(first, last)	<algorithm>	Iterator to maximum element	$O(n)$
min_element(first, last)	<algorithm>	Iterator to minimum element	$O(n)$
accumulate(first, last, init)	<numeric>	Sum of range	$O(n)$
priority_queue<T>	<queue>	Max-heap for greedy selection	$O(\log n)$ push/pop
priority_queue<T, vec, greater<T>>	<queue>	Min-heap	$O(\log n)$ push/pop
set<T> / multiset<T>	<set>	Ordered container for greedy with predecessor/successor	$O(\log n)$ ops
lower_bound(first, last, val)	<algorithm>	First element $\ge$ val in sorted range	$O(\log n)$
upper_bound(first, last, val)	<algorithm>	First element $> $ val in sorted range	$O(\log n)$

---

Implementation (Contest-Ready)

Version 1: Minimal—Activity Selection (Interval Scheduling Maximization)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> a(n); // {end, start}
    for (auto& [e, s] : a) cin >> s >> e;
    sort(a.begin(), a.end());

    int cnt = 0, last = INT_MIN;
    for (auto& [e, s] : a) {
        if (s >= last) {
            cnt++;
            last = e;
        }
    }
    cout << cnt << "\n";
}

Version 2: Explained—Interval Scheduling with Full Trace

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // Store intervals as {end, start} so default pair sort
    // sorts by end time first, breaking ties by start time.
    // This is the key greedy insight: always pick the activity
    // that finishes earliest among compatible ones.
    vector<pair<int,int>> intervals(n);
    for (auto& [end, start] : intervals) {
        cin >> start >> end;
    }

    // Sort by end time (first element of pair).
    // Exchange argument: if greedy picks Y (ends at e_Y) and
    // optimal picks X (ends at e_X >= e_Y) at the same step,
    // swapping X for Y in optimal leaves at least as much room,
    // so greedy never does worse.
    sort(intervals.begin(), intervals.end());

    int count = 0;
    int last_end = INT_MIN; // end time of last selected activity

    for (auto& [end, start] : intervals) {
        // "Compatible" means this activity starts at or after
        // the last selected activity ended.
        // Use >= for closed intervals [start, end],
        // use > if intervals are half-open [start, end).
        if (start >= last_end) {
            count++;
            last_end = end;
        }
    }

    cout << count << "\n";
    return 0;
}

---

Operations Reference

Operation	Time	Space
Sort $n$ items (prerequisite for most greedy)	$O(n\log n)$	$O(\log n)$ stack
Single greedy pass over sorted array	$O(n)$	$O(1)$
Greedy with priority queue (e.g., Huffman)	$O(n\log n)$	$O(n)$
Greedy with set/multiset lookups	$O(n\log n)$	$O(n)$
Exchange-argument proof (your mental effort)	$O(\mathrm{\infty })$	$O(\text{coffee})$

Typical total: $O(n\log n)$ time, $O(n)$ space. The sort dominates; the greedy pass itself is almost always $O(n)$.

---

Problem Patterns & Tricks

Interval Scheduling (Maximum Non-Overlapping)

Sort by end time, greedily pick the earliest-finishing compatible interval. Classic exchange-argument proof.

sort(intervals.begin(), intervals.end()); // {end, start}
int cnt = 0, last = INT_MIN;
for (auto [e, s] : intervals)
    if (s >= last) { cnt++; last = e; }

Problems: CF 1141F2, CSES Movie Festival

Interval Covering (Minimum Intervals to Cover a Range)

Sort by start time. Greedily extend coverage as far right as possible using the best available interval.

  INTERVAL COVERING -- always extend as far right as possible:

  Goal: cover range [L=0, R=10]

  Intervals (sorted by start):
  A: [0-------4)
  B: [1----------6)
  C: [3---------7)
  D: [5-----------9)
  E: [8-----------11)

  Step 1: cur=0. Scan intervals starting <= 0.
          A starts at 0: extends to 4.  best=4.
          PICK A. cur=4.

  Step 2: cur=4. Scan intervals starting <= 4.
          B starts at 1: extends to 6.
          C starts at 3: extends to 7.  best=7.
          PICK C. cur=7.

  Step 3: cur=7. Scan intervals starting <= 7.
          D starts at 5: extends to 9.
          E starts at 8: starts AFTER cur? No, 8 > 7.
          best=9. PICK D. cur=9.

  Step 4: cur=9. Scan intervals starting <= 9.
          E starts at 8: extends to 11 >= R=10. best=11.
          PICK E. cur=11 >= R. DONE.

  Selected: {A, C, D, E} = 4 intervals.

sort(intervals.begin(), intervals.end()); // {start, end}
int cnt = 0, i = 0, cur = L; // L = left boundary to cover
while (cur < R) {             // R = right boundary
    int best = cur;
    while (i < n && intervals[i].first <= cur)
        best = max(best, intervals[i++].second);
    if (best == cur) { /* impossible */ break; }
    cur = best;
    cnt++;
}

Problems: CF 1029C, CSES Movie Festival II

Fractional Knapsack

Sort by value/weight ratio descending. Take as much as possible of each item. Only works for fractional variant (not 0/1).

sort(items.begin(), items.end(), [](auto& a, auto& b) {
    return (double)a.v / a.w > (double)b.v / b.w;
});
double ans = 0, cap = W;
for (auto& [v, w] : items) {
    double take = min(cap, (double)w);
    ans += take * ((double)v / w);
    cap -= take;
    if (cap <= 0) break;
}

Problems: CF 1974C, classical fractional knapsack

Greedy + Sort by Derived Key

Many problems require sorting by a non-obvious key derived from the input. The exchange argument tells you what to sort by: compare two adjacent elements and determine which ordering is better.

Example: Minimize total weighted completion time. Job $i$ has processing time $p_i$ and weight $w_i$. Sort by $p_i/w_i$ ascending (equivalently, $w_i/p_i$ descending).

// Exchange argument: swap adjacent jobs i, j.
// i before j: cost contribution includes w_j * p_i
// j before i: cost contribution includes w_i * p_j
// i before j is better when w_j * p_i < w_i * p_j
// i.e., p_i / w_i < p_j / w_j
sort(jobs.begin(), jobs.end(), [](auto& a, auto& b) {
    return (long long)a.p * b.w < (long long)b.p * a.w;
});

Problems: CF 1203F1, CF 1353D

Greedy with Priority Queue (Huffman-Style)

Repeatedly merge the two smallest (or cheapest) elements. Use a min-heap.

Worked example—tricky case with equal elements:

  Merge costs for a = [2, 2, 3, 3]:

  Heap: {2, 2, 3, 3}

  Step 1: pop 2, 2. Merge cost = 4. Push 4.
          Heap: {3, 3, 4}. Total cost = 4.

  Step 2: pop 3, 3. Merge cost = 6. Push 6.
          Heap: {4, 6}. Total cost = 4 + 6 = 10.

  Step 3: pop 4, 6. Merge cost = 10. Push 10.
          Heap: {10}. Total cost = 4 + 6 + 10 = 20.

  WRONG approach (merge largest first):
  Step 1: merge 3,3 = 6. cost=6.   Heap: {2, 2, 6}
  Step 2: merge 2,6 = 8. cost=14.  Heap: {2, 8}
  Step 3: merge 2,8 = 10. cost=24. Heap: {10}
  Total = 24 > 20.  Merging smallest first wins!

  +-------------------+-------------------+
  | Min-heap (correct) | Max-heap (wrong)  |
  | Total cost = 20    | Total cost = 24   |
  +-------------------+-------------------+

priority_queue<long long, vector<long long>, greater<>> pq;
for (int x : a) pq.push(x);
long long cost = 0;
while (pq.size() > 1) {
    long long x = pq.top(); pq.pop();
    long long y = pq.top(); pq.pop();
    cost += x + y;
    pq.push(x + y);
}

Problems: CF 1760F, CSES Stick Divisions

Greedy with Regret (Undo Last Choice)

Sometimes greedy needs a "regret" mechanism: make a greedy choice, but allow undoing it later if a better option appears. Typically implemented with a priority queue.

// Hire k workers with minimum cost; can fire and rehire.
priority_queue<int> pq; // max-heap of hired costs
long long total = 0;
sort(workers.begin(), workers.end()); // by some criterion
for (auto& [key, cost] : workers) {
    pq.push(cost);
    total += cost;
    if ((int)pq.size() > k) {
        total -= pq.top(); // undo the most expensive hire
        pq.pop();
    }
}

Problems: CF 1251E2, CF 730I

The Exchange Argument — Proving Your Greedy is Correct

Most greedy ideas that "feel right" are wrong. At CF 1400+ you will routinely encounter problems where a plausible greedy fails on a hidden edge case. The exchange argument is a reusable proof framework that lets you either confirm your greedy is correct or discover that it isn't—before you waste 45 minutes coding the wrong approach.

If you cannot construct the exchange argument in under two minutes of mental effort, treat that as strong evidence the problem needs DP. This framework is your single most valuable meta-tool for greedy problems.

The Framework (Four Steps)

1. Assume an optimal solution $\text{OPT}$ exists that differs from your greedy solution $G$.
2. Locate the first position $i$ where $\text{OPT}$ and $G$ differ. $\text{OPT}$ chose element $o$ at position $i$; $G$ chose element $g$.
3. Swap: Construct ${\text{OPT}}^{\prime }$ by replacing $o$ with $g$ at position $i$ in $\text{OPT}$. Show two things:
   • Feasibility: ${\text{OPT}}^{\prime }$ is still a valid solution.
   • Non-worsening: $\text{cost}({\text{OPT}}^{\prime })\le \text{cost}(\text{OPT})$ (or $\ge$ for maximization).
4. Induct: Each swap makes $\text{OPT}$ agree with $G$ on one more position without degrading quality. After finitely many swaps, $\text{OPT}$ becomes $G$. Therefore $G$ is optimal. $◻$

The key intellectual work happens in step 3—that is where the sorting criterion earns its keep.

Worked Example 1: Activity Selection (Interval Scheduling Maximization)

Problem: Given $n$ intervals $[s_i,e_i)$, select the maximum number of non-overlapping intervals.

Greedy rule: Always pick the interval that ends earliest among those compatible with the last selected interval.

Exchange argument:

Let $G=\{g_1,g_2,\dots ,g_k\}$ (sorted by end time) be the greedy solution and $\text{OPT}=\{o_1,o_2,\dots ,o_m\}$ be an optimal solution with $m\ge k$. Find the first index $j$ where $o_j\ne g_j$. By greedy's rule, $e(g_j)\le e(o_j)$ (greedy picked the earliest-finishing compatible interval).

Replace $o_j$ with $g_j$ in $\text{OPT}$:

  Timeline
  ──────────────────────────────────────────►

  OPT:   ├── o_{j-1} ──┤     ├──── o_j ────┤  ├── o_{j+1} ──┤
                                                 ↑ still compatible
  Swap:  ├── o_{j-1} ──┤  ├─ g_j ─┤           ├── o_{j+1} ──┤
                              ↑                  ↑ g_j ends earlier,
                         ends earlier             so gap is even wider

• Feasibility: $g_j$ starts after $o_{j-1}$ ends (same as $o_j$ did, since $G$ and $\text{OPT}$ agreed up to $j-1$). And $g_j$ ends no later than $o_j$, so $o_{j+1}$ is still compatible.
• Non-worsening: We replaced one interval with one interval—same count.

After at most $k$ such swaps, $\text{OPT}$ becomes $G$, so $m=k$ and $G$ is optimal.

Worked Example 2: Minimum Coins (Canonical vs Non-Canonical Systems)

Problem: US coin system $\{25,10,5,1\}$. Make change for amount $N$ using the fewest coins.

Greedy rule: Always use the largest denomination that fits.

Exchange argument sketch: Suppose $\text{OPT}$ uses a smaller coin $c_s$ somewhere that greedy would have replaced with a larger coin $c_l$. Since the US denominations are canonical (every denomination divides or is well-separated from the next), replacing several small coins with the corresponding large coin always reduces total count without changing the sum. For example, replacing five 5¢ coins with one 25¢ coin reduces count by 4. This works for every adjacent denomination pair in $\{25,10,5,1\}$.

Counterexample—non-canonical system $\{1,3,4\}$, amount $=6$:

  Greedy:   4 + 1 + 1 = 3 coins     <- picks largest first
  Optimal:  3 + 3     = 2 coins     <- fewer coins!

Try the exchange argument: $\text{OPT}$ uses coin $o=3$; greedy wants $g=4$. Replacing $o$ with $g$ gives sum $4+3=7>6$—the swap overshoots. We need an extra coin to compensate, making ${\text{OPT}}^{\prime }$ worse, not better. The swap is not cost-neutral, so step 3 fails. The exchange argument correctly exposes the greedy as flawed.

When the Exchange Argument Fails—Use DP

If you sit down to write the swap argument and:

• the swap breaks feasibility (changes the sum, violates a constraint), or
• the swap worsens cost (you need extra compensating moves),

then your greedy is almost certainly wrong. This is not a failure of technique—it is the framework doing its job. The problem likely has optimal substructure but not the greedy-choice property, which is the textbook signature of a DP problem.

Rule of thumb: if a greedy choice at step $i$ can invalidate or constrain choices at steps $i+2,i+3,\dots$ in ways you cannot bound, you need to track that state—and that means DP. See DP vs Greedy Guide for a side-by-side decision framework.

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|  GREEDY CHEAT SHEET                                          |
+--------------------------------------------------------------+
|  WHEN TO USE:                                                |
|  - "maximize/minimize" + no DP substructure visible          |
|  - exchange argument works for adjacent elements             |
|  - problem screams "sort then scan"                          |
+--------------------------------------------------------------+
|  RECIPE:                                                     |
|  1. Identify the greedy criterion (what to sort by)          |
|  2. Prove via exchange argument (swap two adjacent)          |
|  3. Sort + single pass (or sort + priority queue)            |
+--------------------------------------------------------------+
|  KEY PATTERNS:                                               |
|  - Interval scheduling  -> sort by END time                  |
|  - Interval covering    -> sort by START time                |
|  - Fractional knapsack  -> sort by VALUE/WEIGHT desc         |
|  - Weighted scheduling  -> sort by p_i/w_i asc              |
|  - Merge cheapest       -> min-heap (Huffman)                |
|  - Regret/undo          -> greedy + max-heap for removal     |
+--------------------------------------------------------------+
|  COMPLEXITY: O(n log n) sort + O(n) pass = O(n log n)        |
|  SPACE:      O(n) for input, O(1)-O(n) extra                |
+--------------------------------------------------------------+
|  DANGER:                                                     |
|  - Can't prove exchange arg? Probably need DP.               |
|  - 0/1 knapsack is NOT greedy.                               |
|  - Ties in sort key: define tiebreaker or prove it irrelevant|
+--------------------------------------------------------------+

---

Gotchas & Debugging

Greedy Is Wrong (Most Common Bug)

The judge found a counterexample before you did. When a greedy solution gets WA, the right move is to construct that counterexample yourself—not to tweak the comparator and resubmit. Compare greedy output against brute force on random small inputs:

  Is your greedy correct? Follow this check:

  Greedy solution
       |
       v
  Try exchange argument (2 min)
       |
  +----+----+
  |         |
  WORKS    FAILS --> Stop. Use DP.
  |
  v
  Stress test vs brute force
       |
  +----+----+
  |         |
  MATCH    MISMATCH --> Found counterexample!
  |                     Analyze and fix sort key.
  v
  Submit with confidence

// Stress test: brute force vs greedy
for (int iter = 0; iter < 100000; iter++) {
    auto input = gen_random();
    auto ans_brute = brute(input);
    auto ans_greedy = greedy(input);
    if (ans_brute != ans_greedy) {
        print(input); // found counterexample
        break;
    }
}

Wrong Sorting Comparator

Custom comparators must define a strict weak ordering: if cmp(a, b) is true, cmp(b, a) must be false. Using <= instead of < causes undefined behavior in sort.

// WRONG: causes UB with equal elements
sort(a.begin(), a.end(), [](int x, int y) { return x <= y; });

// CORRECT:
sort(a.begin(), a.end(), [](int x, int y) { return x < y; });

Integer Overflow in Comparator

When sorting by a ratio like $p_i/w_i$, avoid floating-point. Cross-multiply instead:

// WRONG: floating-point precision issues
sort(a.begin(), a.end(), [](auto& x, auto& y) {
    return (double)x.p / x.w < (double)y.p / y.w;
});

// CORRECT: cross-multiply (watch for overflow -> use long long)
sort(a.begin(), a.end(), [](auto& x, auto& y) {
    return (long long)x.p * y.w < (long long)y.p * x.w;
});

Closed vs Open Intervals

Interval scheduling: does [1, 3] overlap with [3, 5]? Depends on the problem. Read carefully whether endpoints are inclusive. Use >= for [closed, closed] and > for [closed, open).

Not Handling Equal Elements

When two elements have the same greedy key, the tiebreaker can matter. Example: if sorting by deadline and two jobs share a deadline, processing order between them might affect feasibility.

Forgetting to Use long long

Greedy accumulation (sums, costs) often overflows int. If $n\le 2\times {10}^5$ and values $\le {10}^9$, the sum can reach $2\times {10}^{14}$.

long long total = 0; // NOT int
for (auto& x : a) total += x;

Greedy on Multisets—Erasing by Value

When using multiset in a greedy algorithm, ms.erase(val) removes all copies. Erase one copy with:

auto it = ms.find(val);
if (it != ms.end()) ms.erase(it); // erase ONE copy

Mental Traps

"I can construct the exchange argument after coding." The exchange argument must come before coding, not as a post-hoc justification. Code first and you will rationalize your approach. Confirmation bias is powerful: once you've spent 20 minutes on an implementation, your brain will find a way to believe the proof holds even when it doesn't.

  WRONG workflow:                 RIGHT workflow:

  Read problem                    Read problem
       |                               |
       v                               v
  "Looks greedy"                  "Looks greedy"
       |                               |
       v                               v
  CODE (20 min)                   EXCHANGE ARGUMENT (2 min)
       |                               |
       v                          +----+----+
  Submit --> WA                   |         |
       |                         WORKS    FAILS
       v                          |         |
  "Let me prove it..."           CODE     --> DP
       |                        (15 min)
       v
  Can't prove it,
  wasted 20 min

"If I can't find a counterexample, it must be correct." Failure to find a counterexample is not a proof—it is just evidence that your manual tests weren't adversarial enough. Some greedy algorithms fail only on inputs that are hard to construct by hand. The exchange argument provides the actual proof; manual testing provides only false confidence.

  "No counterexample found" != "Correct"

  Example: Coin change with {1, 3, 4}, target = 6

  Quick manual tests:
    target=1: greedy 1       optimal 1       MATCH
    target=3: greedy 3       optimal 3       MATCH
    target=4: greedy 4       optimal 4       MATCH
    target=5: greedy 4+1     optimal 3+1+1?  No, 4+1=2 coins. MATCH

  "All tests pass, greedy works!"

    target=6: greedy 4+1+1=3 coins
              optimal 3+3  =2 coins   <-- FAILS!

  The counterexample wasn't in your quick tests.
  Exchange argument would have caught this:
    Swap coin 3 for coin 4 --> sum overshoots --> STEP 3 FAILS

"This problem looks like interval scheduling." Many greedy problems superficially resemble interval scheduling (sort + scan). But the specific criterion—what to sort by, what makes a choice "compatible"—depends on the exact problem. Misidentifying the pattern and applying the wrong sorting key is a common failure.

  Same structure, DIFFERENT sort keys:

  +---------------------------+-------------------+
  | Problem                   | Sort by           |
  +---------------------------+-------------------+
  | Max non-overlapping       | END time (asc)    |
  | Min intervals to cover    | START time (asc)  |
  | Min lateness              | DEADLINE (asc)    |
  | Min weighted completion   | p_i/w_i (asc)    |
  +---------------------------+-------------------+

  Using "sort by end time" on a deadline problem = WA.
  The exchange argument tells you WHICH key is correct.

---

Self-Test

Before moving on, verify you can do these without looking at notes:

• [ ] State the exchange argument template (4 steps) from memory and apply it to a new problem: "schedule $n$ jobs with durations, minimize total completion time."
• [ ] Explain why 0/1 knapsack fails with greedy but fractional knapsack doesn't—using the concept of "state" and "irrevocable choices."
• [ ] Write the greedy for "interval scheduling maximization" (sort by end time, scan), verify it on a 5-interval example.
• [ ] Name the bug in sort(a, a+n, [](auto x, auto y){ return x.ratio <= y.ratio; }) and fix it.
• [ ] Describe the "greedy with regret" pattern using a priority queue—when is it needed and what does it look like?
• [ ] Given two adjacent jobs with $(p_1=3,w_1=2)$ and $(p_2=1,w_2=5)$, derive which order is better using cross-multiplication.

Socratic Checkpoints

Checkpoint: How do you prove a greedy algorithm is correct?

Think, then click

The two standard techniques are the exchange argument and the greedy stays ahead lemma. In the exchange argument, you take any optimal solution that differs from the greedy solution, find the first point of difference, and show that swapping to match the greedy choice doesn't make the solution worse—eventually transforming OPT into the greedy solution without losing optimality. In "greedy stays ahead," you prove by induction that after each step, the greedy solution is at least as good as any other solution at that point. Both approaches require identifying what "greedy choice" means and why it's safe.

Checkpoint: When does a greedy approach fail, and how can you recognize it?

Think, then click

Greedy fails when a locally optimal choice leads to a globally suboptimal solution—i.e., when you need to "sacrifice now to gain later." Classic warning signs: (1) the problem has overlapping subproblems (suggests DP instead), (2) small examples exist where the greedy choice doesn't lead to the best answer (always test on 3–4 cases!), (3) the problem requires combining items with complex interactions (e.g., 0/1 knapsack—taking a lighter item now may block a more valuable heavy item later). If you can't construct an exchange argument, it's likely not greedy.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Minimize the Permutation	CF 1256A	800	Greedy swap to minimize lexicographic order
2	Ehab and another construction	CF 1088B	1000	Simple greedy construction
3	Movie Festival	CSES	1200	Classic interval scheduling, sort by end
4	Tasks and Deadlines	CSES	1300	Sort by duration, exchange argument proof
5	Stick Divisions	CSES	1400	Reverse Huffman—min-heap merge
6	Making a String	CF 1353D	1400	Greedy sort by cost, accumulate
7	Two Divisors	CF 1366D	1500	Greedy factorization + construction
8	Playlist	CF 1141F2	1600	Sort + greedy selection with constraints
9	Buses on a Staircase	CF 1029C	1700	Interval covering / greedy scan
10	Voting	CF 1251E2	1800	Greedy with regret, priority queue

---

Designing Test Cases

Greedy solutions either work perfectly or fail catastrophically—there's rarely a middle ground. The goal of testing is to find the counterexample before the judge does.

Minimal cases:

• Empty input: n = 0. Does your code handle it without crashing? Many greedy solutions skip this and segfault on a[0].
• Single element: n = 1. The answer is usually trivial. Verifies your loop/sort doesn't break on degenerate input.

Edge cases:

• All equal elements: a = [5, 5, 5, 5]. Many greedy comparators behave differently when elements are tied—especially if your sort isn't stable or your comparator isn't strict weak ordering.
• Already sorted / reverse sorted: If your greedy relies on sorting, test what happens when input is already in the "right" or "wrong" order.
• Adversarial case designed to break wrong greedy: This is the most important test. Think: "What would break the first greedy idea I had?" For example, in activity selection, an interval that starts earliest but is extremely long. In coin change, denominations that aren't powers of each other.
• Duplicates in the decision criterion: Two items with the same priority but different secondary attributes.

Stress test (run locally before submitting):

// Compare greedy answer against brute force for small inputs.
mt19937 rng(42);
for (int iter = 0; iter < 100000; iter++) {
    int n = rng() % 10 + 1;
    // generate random problem instance (items, intervals, etc.)
    int greedy_ans = solve_greedy(/* ... */);
    int bf_ans = solve_brute(/* ... */);  // try all n! permutations or 2^n subsets
    assert(greedy_ans == bf_ans);
}

Keep n <= 10 so brute force over permutations (10! ~= 3.6M) or subsets (2^{10} = 1024) stays fast. If the assert fires, you've found a counterexample—print it, study it, and fix your greedy (or switch to DP).

Pro tip: When your greedy passes the stress test but you're not sure about correctness, try n <= 15 with 1M iterations. If it survives, your greedy is almost certainly correct—or the counterexample is very rare and unlikely to appear in judge tests.

---

Further Reading

The core insight of greedy is deceptively simple: if making the locally optimal choice at every step never needs to be undone, the strategy is globally optimal. The hard part is not the code—it is proving (via exchange argument) that "local beats global." The fingerprint to recognize: optimization problem + sorting reveals a "never regret" ordering → greedy. A useful mnemonic: "Sort, grab the best, never look back—but prove it first."

Greedy algorithms have ancient roots (the coin-change heuristic was used by merchants for centuries) and were formally analyzed by Jack Edmonds in the 1960s through matroid theory, which characterizes exactly when greedy gives optimal solutions. The classic activity selection proof appears in Cormen et al.'s Introduction to Algorithms (1990).

• cp-algorithms: Greedy algorithms—general reference for exchange arguments and scheduling.
• CF Blog: Greedy problems and exchange arguments—community discussion of proof techniques.
• USACO Guide: Greedy with Sorting—introductory greedy problems with editorial.
• Jeff Erickson: Greedy Algorithms (textbook chapter)—rigorous treatment of exchange arguments and matroids.

Cross-references in this guidebook:

• Sorting and Searching—prerequisite; most greedy starts with a sort.
• Binary Search—greedy + binary search is a common combined technique.
• Coordinate Compression—next topic; often paired with greedy on intervals.
• Dynamic Programming—1D Introduction—when greedy fails, DP is usually the answer.
• Contribution Technique—when the "greedy" intuition is really about counting contributions.
• DP vs Greedy Guide—systematic guide for choosing between the two.

---

Rating Progression

• CF 1200: Sort by one criterion and iterate: interval scheduling by end time, coin change with largest denomination first.
• CF 1500: Exchange argument proofs; sort by ratio or custom comparator; greedy + binary search hybrid.
• CF 1800: Greedy with regret (priority queues to undo decisions); multi-criteria greedy with tiebreakers; greedy on trees.
• CF 2100: Matroid intersection; greedy + DP hybrid where greedy handles one dimension; adversarial greedy arguments.

Before You Code Checklist

• [ ] Identified the greedy criterion: what am I sorting by, and why is that ordering optimal?
• [ ] Sketched an exchange argument: if I swap two adjacent elements in my ordering, does the answer get worse (or at least not better)?
• [ ] Checked for counterexamples: does a small hand-crafted input break the greedy? (Try 3-5 elements.)
• [ ] Verified the comparator is a strict weak ordering (irreflexive, transitive, asymmetric)—broken comparators cause undefined behavior in sort.
• [ ] Considered whether greedy is correct at all—could this be a DP or flow problem in disguise?

What Would You Do If...?

1. Your greedy passes all samples but fails on a hidden test with just 4 elements—how would you systematically find a counterexample?
2. You realize mid-contest that your greedy needs to "undo" a previous choice—what data structure supports this "greedy with regret" pattern?
3. The problem has two competing objectives (minimize cost and maximize coverage)—when does greedy still work, and when must you switch to DP?

The Mistake That Teaches

A contestant sorted jobs by deadline for a scheduling problem, greedily assigning each to the latest available slot. It passed samples and even stress tests up to $n=10$. At $n={10}^5$, it gave wrong answers because the correct criterion was sorting by penalty (not deadline). The exchange argument would have caught this: swapping two jobs sorted by penalty always worsens the total cost, but swapping two sorted by deadline does not. The lesson—never skip the proof, even when the greedy "feels obvious."

Debug This

Bug 1:

// Interval scheduling: pick max non-overlapping intervals
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
    return a.start < b.start;  // Bug: wrong sort key
});
int cnt = 0, last_end = -1;
for (auto& [s, e] : intervals) {
    if (s >= last_end) { cnt++; last_end = e; }
}

Answer

Should sort by end time, not start time. Sorting by start time doesn't guarantee maximum non-overlapping intervals—a long interval starting early can block many short ones. The classic proof requires earliest-end-time-first.

Bug 2:

// Custom comparator for sorting
sort(a.begin(), a.end(), [](int x, int y) {
    return x <= y;  // Bug here
});

Answer

The comparator uses <= instead of <. This violates strict weak ordering (it's not irreflexive: comp(x, x) returns true). This is undefined behavior in C++ and can cause crashes, infinite loops, or wrong output depending on the STL implementation.

Bug 3:

// Greedy: assign tasks to minimize max lateness
// Each task has processing time p[i] and deadline d[i]
sort(tasks.begin(), tasks.end(), [](auto& a, auto& b) {
    return a.d - a.p < b.d - b.p;  // Bug: wrong criterion
});
int time = 0, max_late = 0;
for (auto& t : tasks) {
    time += t.p;
    max_late = max(max_late, time - t.d);
}

Answer

To minimize maximum lateness, sort by deadline d alone (Earliest Deadline First), not by d - p. The EDF ordering is provable via exchange argument; sorting by slack d - p does not yield optimal results.

---

Code Reading Exercise

What does this code compute? Read it carefully before checking the answer.

int solve(vector<pair<int, int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](auto& a, auto& b) { return a.second < b.second; });
    int count = 0, last = INT_MIN;
    for (auto& [s, e] : intervals) {
        if (s >= last) {
            count++;
            last = e;
        }
    }
    return count;
}

Answer

This finds the maximum number of non-overlapping intervals (the activity selection problem). Sorting by end time and greedily picking the earliest-finishing compatible interval is provably optimal via exchange argument. The condition `s >= last` treats intervals sharing an endpoint as non-overlapping. This runs in O(n log n) due to the sort.

---

What does this code compute?

bool solve(vector<int>& a) {
    int n = a.size(), reach = 0;
    for (int i = 0; i < n; i++) {
        if (i > reach) return false;
        reach = max(reach, i + a[i]);
    }
    return reach >= n - 1;
}

Answer

This determines whether you can reach the last index of the array, where a[i] is the maximum jump length from position i (the "Jump Game" problem). The greedy insight: maintain the farthest reachable index. At each position, if you haven't been reached (i > reach), it's impossible. Otherwise, extend the reach. No backtracking needed—O(n) time.

What to Solve Next

• Complete Search—when greedy fails, brute force with pruning is the safety net.
• DP vs Greedy Guide—side-by-side comparison for when you're unsure.
• Practice Ladder—drill greedy problems by rating.

---

Solve With Me — CF 1325D "Ehab the Xor-ist"

Problem: find the shortest array whose elements XOR to $u$ and sum to $v$. Elements must be positive.

Immediate observations: XOR of all elements is $u$, sum is $v$. If $u>v$—impossible, because XOR can't exceed the sum (each bit in the XOR must be "supported" by at least one element). Also, $u$ and $v$ must have the same parity: XOR gives the parity of the sum of least-significant bits, but more precisely—if all elements sum to $v$, their XOR and sum must agree modulo 2. Quick check: $u\equiv v(\mathrm{mod}2)$ must hold. If not, output $-1$.

Now the greedy construction. Simplest case: can I do it with one element? Only if $u=v$. That element is just $u$. Done.

Otherwise, can I always do it with two elements? I need $a\oplus b=u$ and $a+b=v$. From XOR and sum: $a+b=(a\oplus b)+2(a\mathrm{\&}b)$, so $v=u+2(a\mathrm{\&}b)$. That gives $a\mathrm{\&}b=(v-u)/2$. For this to be valid, $(v-u)$ must be even (already guaranteed by parity check) and $a\mathrm{\&}b$ must not conflict with $a\oplus b$—meaning no bit is set in both. Check: $(u\mathrm{\&}\frac{v-u}{2})=0$?

We have $a\oplus b=u$ and $a\mathrm{\&}b=c$ where $c=(v-u)/2$. Since XOR gives bits where $a$ and $b$ differ, and AND gives bits where both are 1, these must be disjoint: $(u\mathrm{\&}c)=0$. If so, set $a=u\mid c$ (same as $u+c$ since they share no bits) and $b=c$. Then $a\oplus b=(u\mid c)\oplus c=u$ and $a+b=u+c+c=u+2c=v$. Correct.

What if $(u\mathrm{\&}c)\ne 0$? Yes, it can happen: take $u=3$ (binary 11), $v=5$, then $c=1$ (binary 01) and $u\mathrm{\&}c=01\ne 0$. Two elements won't work in this case.

Three elements: $[u,\frac{v-u}{2},\frac{v-u}{2}]$. XOR: $u\oplus k\oplus k=u$ OK. Sum: $u+2k=u+(v-u)=v$ OK. And all elements are positive as long as $u>0$ and $k>0$, which holds when $u\ne v$ and $v>u$. Worst case answer is 3.

So the algorithm: if $u=v$, answer is $[u]$. Else if parity differs or $u>v$, answer is $-1$. Else compute $c=(v-u)/2$; if $(u\mathrm{\&}c)=0$, answer is $[u+c,c]$. Otherwise answer is $[u,c,c]$.

What to recognize next time: When a problem asks you to construct elements with a given XOR and sum, the identity $a+b=(a\oplus b)+2(a\mathrm{\&}b)$ is the master key. Greedy here means: try 1 element, then 2, then 3—you never need more than 3.