Chapter 4.1: Greedy Fundamentals

📝 Before You Continue: You should be comfortable with sorting (Chapter 3.3) and basic priority_queue usage (Chapter 3.1). Some problems also use interval reasoning.

A greedy algorithm is like a traveler who always takes the nearest oasis — no map, no planning, just the best move visible right now. For the right problems, this always works out. For others, it leads to disaster.

## 📚 Table of Contents

💡 Suggested reading path: First-time readers should work through §4.1.1–4.1.5 in order. Sections §4.1.6–4.1.9 can be read in any order. Sections §4.1.11–4.1.13 are advanced techniques for USACO Gold and above.

4.1.1 What Makes a Problem "Greedy-Solvable"?

A greedy approach works when the problem has the greedy choice property: making the locally optimal choice at each step leads to a globally optimal solution.

Contrast with DP

Consider making change for 11 cents:

• Coins: {1, 5, 6, 9}
• Greedy: 9 + 1 + 1 = 3 coins
• Optimal: 6 + 5 = 2 coins

Here greedy fails. The greedy choice (always take the largest coin) doesn't lead to the global optimum.

But with US coins {1, 5, 10, 25, 50}:

• 41 cents: Greedy → 25 + 10 + 5 + 1 = 4 coins ✓ (optimal)

US coins have a special structure that makes greedy work. Always verify!

Complete Walkthrough: Coin Change — Greedy vs DP

Let's trace through the coin change example in detail to see exactly where greedy goes wrong.

Problem: Make change for 11 cents using coins {1, 5, 6, 9}. Minimize the number of coins.

Greedy approach (always pick the largest coin ≤ remaining amount):

Remaining = 11 → Pick 9 (largest ≤ 11).  Remaining = 11 - 9 = 2.  Coins used: [9]
Remaining = 2  → Pick 1 (largest ≤ 2).   Remaining = 2 - 1 = 1.   Coins used: [9, 1]
Remaining = 1  → Pick 1 (largest ≤ 1).   Remaining = 1 - 1 = 0.   Coins used: [9, 1, 1]
Result: 3 coins ✗

Optimal (DP) approach:

6 + 5 = 11.  Coins used: [6, 5]
Result: 2 coins ✓

Why did greedy fail? Greedy grabbed the biggest coin (9) immediately, leaving a remainder (2) that can only be filled with 1-cent coins. It couldn't "see" that skipping 9 and using 6 + 5 would be better overall.

Now contrast with US coins {1, 5, 10, 25} for 41 cents:

Remaining = 41 → Pick 25.  Remaining = 16.  Coins: [25]
Remaining = 16 → Pick 10.  Remaining = 6.   Coins: [25, 10]
Remaining = 6  → Pick 5.   Remaining = 1.   Coins: [25, 10, 5]
Remaining = 1  → Pick 1.   Remaining = 0.   Coins: [25, 10, 5, 1]
Result: 4 coins ✓ (optimal!)

US coins work because each denomination is at least twice the previous one — you never need to "undo" a greedy choice. With {1, 5, 6, 9}, the denominations 5 and 6 are too close together, creating situations where the greedy choice blocks a better combination.

⚠️ Takeaway: Coin change is the classic example of a problem that looks greedy but isn't always. Unless the coin denominations have a special structure (like US coins), you need DP. When in doubt, try a small counterexample!

💡 Key Insight: Greedy works when there's a "no regret" property — once you make the greedy choice, you'll never need to undo it. If you can always swap any non-greedy choice for the greedy one without making things worse, greedy is optimal.

Greedy vs DP Decision Path Comparison:

🔍 How to Recognize a Greedy Problem

When you see a new problem, run through this checklist:

1. Is there a natural "ordering" or "priority" to process elements?
   (e.g., sort by deadline, end time, ratio, size...)
        ↓ YES
2. Can you prove that the locally optimal choice is globally safe?
   (exchange argument: swapping greedy choice for any other never helps)
        ↓ YES
3. Can you find a small counterexample where greedy fails?
        ↓ NO counterexample found
   → Greedy is likely correct. Implement and verify.
        ↓ Counterexample found
   → Greedy fails. Consider DP or other approaches.

Three signals that suggest greedy:

• ① After sorting, there's a clear "process in this order" rule
• ② The problem asks to maximize/minimize a count or cost with a single pass
• ③ Subproblems are independent — choosing one element doesn't affect the "shape" of remaining choices

Three signals that suggest DP instead:

• ① Choices interact (picking A changes what's available for B)
• ② You need to consider multiple future states
• ③ You can find a counterexample for any greedy rule you try

4.1.2 The Exchange Argument

The exchange argument is the standard proof technique for greedy algorithms. It answers the question: "How do I prove my greedy is correct?" almost every greedy correctness proof at USACO uses this technique.

How It Works

The proof template has four steps:

1. Assume there exists an optimal solution O that makes a different choice from our greedy algorithm at some step.
2. Identify the first position where O and greedy differ.
3. Swap greedy's choice into O's solution at that position. Show that the result is at least as good (cost doesn't increase, or count doesn't decrease).
4. Repeat until O has been fully transformed into the greedy solution. Since each swap maintains or improves the solution, the greedy solution must be optimal.

💡 Key Insight: You do not need to show greedy is uniquely optimal — just that no swap can improve on it. Even if multiple solutions achieve the same optimum, greedy reaches one of them.

📋 Exchange Argument Proof Template

Given: Greedy rule G, optimal solution O.

Step 1 — Find a difference: Let i be the first index where O differs from G.

Step 2 — Swap: Construct O' by replacing O's choice at position i with G's choice.

Step 3 — Compare: Show cost(O') ≤ cost(O) (or count(O') ≥ count(O)).

Step 4 — Conclude: By induction, repeatedly swapping transforms O into G without worsening the solution. Therefore G is optimal.

Why "Adjacent Swaps" Are Enough

A crucial observation: if you can show that swapping any two adjacent out-of-order elements doesn't worsen the solution, then by a standard "bubble sort" argument, you can rearrange any solution into the greedy order without ever making things worse.

This is why the exchange argument almost always focuses on swapping just two adjacent elements — the full proof follows by induction.

Concrete Example: Scheduling to Minimize Weighted Sum

Problem: You have N jobs. Job i has processing time t[i] and weight w[i]. All jobs run on one machine sequentially. The weighted completion time of job i = w[i] × (sum of processing times of all jobs up to and including job i). Minimize the total weighted completion time.

Sample Input:

3
2 3
1 5
4 2

(format: t[i] w[i] per line)

Sample Output:

37

What order is optimal? Use the exchange argument:

Consider two adjacent jobs A (processing time a, weight w_A) and B (processing time b, weight w_B). Let S be the total processing time of all jobs scheduled before these two. Then:

A → B is better when: w_B·a < w_A·b, i.e., w_A/t_A > w_B/t_B (higher weight/time ratio goes first).

Greedy rule: sort jobs by w[i]/t[i] in descending order.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int,int>> jobs(n);  // {t, w}
    for (auto &[t, w] : jobs) cin >> t >> w;

    // Sort by w/t ratio descending (higher ratio goes first)
    sort(jobs.begin(), jobs.end(), [](const auto &a, const auto &b) {
        // a.second/a.first > b.second/b.first  →  a.second * b.first > b.second * a.first
        return (long long)a.second * b.first > (long long)b.second * a.first;
    });

    long long total = 0, curTime = 0;
    for (auto [t, w] : jobs) {
        curTime += t;
        total += (long long)w * curTime;
    }

    cout << total << "\n";
    return 0;
}
// Time complexity: O(N log N)

Trace for the sample:

Jobs: (t=2,w=3), (t=1,w=5), (t=4,w=2)
w/t ratios: 3/2=1.5,  5/1=5.0,  2/4=0.5

Sorted (w/t desc): (t=1,w=5), (t=2,w=3), (t=4,w=2)

curTime=1:  cost += 5×1  =  5
curTime=3:  cost += 3×3  =  9
curTime=7:  cost += 2×7  = 14
Total = 5 + 9 + 14 = 28

(Note: the sample above uses different weights — trace matches the actual input provided)

Visual: Greedy Exchange Argument

The diagram illustrates the exchange argument: if two adjacent elements are "out of order" relative to the greedy criterion, swapping them produces a solution that is at least as good. By repeatedly applying swaps we can transform any solution into the greedy solution without losing value.

When the Exchange Argument Fails

Sometimes you cannot find a valid exchange — this signals that greedy won't work:

• 0/1 Knapsack: You can't swap a whole item for a fraction of another, so the exchange doesn't preserve the constraint.
• Coin change with arbitrary denominations: Swapping coin choices can actually force more coins in other positions.
• General weighted interval scheduling: Picking a high-profit short job might block two medium-profit jobs that together exceed it.

In all these cases, the exchange argument breaks down, and DP is required instead.

The Exchange Argument Checklist

Before using greedy, ask:

• Can I define a total order on elements?
• If two adjacent elements are "out of order," can I swap them without increasing cost?
• Does the cost change only depend on the relative order of the two swapped elements (not on what surrounds them)?

If all three hold, the exchange argument goes through and greedy is provably optimal.

Let's see this in action across the major interval and scheduling problems.

4.1.3 Activity Selection Problem

Problem: You are given N activities, each with a start time s[i] and finish time f[i]. Only one activity can run at a time. Two activities conflict if they overlap (one starts before the other finishes). Select the maximum number of non-overlapping activities.

Input format:

N
s[1] f[1]
s[2] f[2]
...
s[N] f[N]

6
1 3
2 5
3 9
6 8
5 7
8 11

3

Constraints: 1 ≤ N ≤ 10^5, 0 ≤ s[i] < f[i] ≤ 10^9

Why This Is Greedy-Solvable

Intuitively: among all activities that start after your last chosen one, which one should you pick next? The one that ends soonest — it "uses up" the least future time and leaves the most room for subsequent activities.

Any other choice (picking an activity that ends later) can only hurt: it blocks at least as many future activities as the earliest-ending choice, and possibly more.

This is the greedy choice property: the locally optimal choice (pick earliest-ending compatible activity) leads to a globally optimal solution.

Visual: Activity Selection Gantt Chart

The Gantt chart shows all activities on a timeline. Selected activities (green) are non-overlapping and maximally many. Rejected activities (gray) are skipped because they overlap with an already-selected one. The greedy rule is: always pick the activity with the earliest end time that doesn't conflict.

Greedy Algorithm:

1. Sort activities by end time
2. Always select the activity that ends earliest among those compatible with previously selected activities

Activity Selection Greedy Process Illustration:

💡 Why sort by end time? Selecting the earliest-ending activity leaves the most time for subsequent activities. Sorting by start time might select an activity that starts early but ends very late, occupying a large amount of time.

// Solution: Activity Selection — O(N log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int,int>> activities(n);  // {end_time, start_time}
    for (int i = 0; i < n; i++) {
        int s, f;
        cin >> s >> f;
        activities[i] = {f, s};  // sort by end time
    }

    sort(activities.begin(), activities.end());  // ← KEY LINE: sort by end time

    int count = 0;
    int lastEnd = -1;  // end time of the last selected activity

    for (auto [f, s] : activities) {
        if (s >= lastEnd) {      // this activity starts after the last one ends
            count++;
            lastEnd = f;         // update last end time
        }
    }

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

Complete Walkthrough: USACO-Style Activity Selection

Problem: Given activities: [(1,3), (2,5), (3,9), (6,8), (5,7), (8,11), (10,12)] (format: start, end)

Step 1 — Sort by end time:

Activity:  A      B      C      D      E      F      G
(s,e):  (1,3)  (2,5)  (5,7)  (6,8)  (3,9)  (8,11) (10,12)

Sorted: A(1,3), B(2,5), C(5,7), D(6,8), E(3,9), F(8,11), G(10,12)

Step 2 — Greedy selection (lastEnd = -1 initially):

Activity A (1,3):  start=1 ≥ lastEnd=-1 ✓ SELECT. lastEnd = 3. Count = 1
Activity B (2,5):  start=2 ≥ lastEnd=3? NO (2 < 3). SKIP.
Activity C (5,7):  start=5 ≥ lastEnd=3 ✓ SELECT. lastEnd = 7. Count = 2
Activity D (6,8):  start=6 ≥ lastEnd=7? NO (6 < 7). SKIP.
Activity E (3,9):  start=3 ≥ lastEnd=7? NO (3 < 7). SKIP.
Activity F (8,11): start=8 ≥ lastEnd=7 ✓ SELECT. lastEnd = 11. Count = 3
Activity G (10,12):start=10 ≥ lastEnd=11? NO (10 < 11). SKIP.

Result: 3 activities selected — A(1,3), C(5,7), F(8,11)

ASCII Timeline Diagram:

Time:  0  1  2  3  4  5  6  7  8  9  10 11 12
       |  |  |  |  |  |  |  |  |  |  |  |  |
A:        [===]                                   ✓ SELECTED
B:           [======]                             ✗ overlaps A
C:                   [======]                     ✓ SELECTED
D:                      [======]                  ✗ overlaps C
E:              [============]                    ✗ overlaps A and C
F:                            [======]            ✓ SELECTED
G:                               [======]         ✗ overlaps F

Selected: A ===    C ===    F ===
          1-3      5-7      8-11

Formal Exchange Argument Proof (Activity Selection)

Claim: Sorting by end time and greedily selecting is optimal.

Proof:

Let G = greedy solution, O = some other optimal solution. Both select k activities.

Step 1 — Show first selections can be made equivalent: Let a₁ be the first activity selected by G (earliest-ending activity overall). Let b₁ be the first activity selected by O.

Since G sorts by end time, end(a₁) ≤ end(b₁).

Now "swap" b₁ for a₁ in O: replace b₁ with a₁. Does O remain feasible?

• a₁ ends no later than b₁, so a₁ conflicts with at most as many activities as b₁ did
• All activities in O that came after b₁ and didn't conflict with b₁ also don't conflict with a₁ (since a₁ ends ≤ b₁ ends)
• So O' (with a₁ replacing b₁) is still a valid selection of k activities ✓

Step 2 — Induction: After the first selection, G picks the earliest-ending activity compatible with a₁, and O' has a₁ as its first activity. Apply the same argument to the remaining activities.

Conclusion: By induction, any optimal solution O can be transformed into G (the greedy solution) without losing optimality. Therefore G is optimal. ∎

💡 Key Insight from the proof: The greedy choice (earliest end time) is "safe" because it leaves the most remaining time for future activities. Choosing any later-ending first activity can only hurt future flexibility.

4.1.4 Interval Scheduling Maximization vs. Minimization

This section covers three related interval problems. They look similar but require subtly different greedy strategies.

Visual: Interval Scheduling on a Number Line

The number line diagram shows multiple intervals and the greedy selection process. By sorting by end time and always taking the next non-overlapping interval, we achieve the maximum number of selected intervals. Green intervals are selected; gray ones are rejected due to overlap.

Maximization: Maximum Non-Overlapping Intervals

This is exactly the Activity Selection problem from §4.1.3. Sort by end time, greedy select as above.

5
1 4
2 6
3 5
7 9
8 10

3

5
1 3
2 5
4 6
6 8
7 9

Sample Output:

3

(Selected: [1,3], [4,6], [6,8] — 3 non-overlapping activities.)

Minimization: Minimum "Points" to Stab All Intervals

Problem: Given N intervals on the number line, find the minimum number of "points" (each point is a real number) such that every interval contains at least one point. Two intervals that share only an endpoint are considered to both contain that point.

Input format:

N
l[1] r[1]
l[2] r[2]
...

5
1 4
2 6
3 5
7 9
8 10

2

Greedy strategy: Sort intervals by right endpoint ascending. Maintain lastPoint (the last placed point). For each interval:

• If lastPoint is already inside this interval (lastPoint >= l[i]): this interval is already covered, skip.
• Otherwise: place a new point at r[i] (rightmost possible position, maximizing coverage of future intervals). Increment count.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<pair<int,int>> intervals(n);  // {right, left}
    for (auto &[r, l] : intervals) cin >> l >> r;

    sort(intervals.begin(), intervals.end());  // sort by right endpoint

    int points = 0;
    long long lastPoint = LLONG_MIN;

    for (auto [r, l] : intervals) {
        if (lastPoint < l) {          // current point doesn't cover this interval
            lastPoint = r;            // place new point at right end
            points++;
        }
        // else: already covered, skip
    }

    cout << points << "\n";
    return 0;
}
// Time complexity: O(N log N)

Step-by-step trace:

Sorted by right endpoint: [1,4], [3,5], [2,6], [7,9], [8,10]

lastPoint = -∞:
[1,4]:  -∞ < 1 → new point at 4.  lastPoint=4, count=1
[3,5]:  4 ≥ 3 → already covered, skip.
[2,6]:  4 ≥ 2 → already covered, skip.
[7,9]:  4 < 7 → new point at 9.   lastPoint=9, count=2
[8,10]: 9 ≥ 8 → already covered, skip.

Answer: 2 ✓

💡 Why place the point at the right endpoint? Among all valid positions for a new point (anywhere in the current uncovered interval), the rightmost position covers the most subsequent intervals (those that start before or at r[i]). This is the greedy choice.

Minimization: Minimum Intervals to Cover a Range

Problem: Given N intervals and a target range [0, T], select the minimum number of intervals from the set such that their union completely covers [0, T]. If impossible, output "Impossible".

Input format:

T N
l[1] r[1]
l[2] r[2]
...

10 5
0 4
3 6
5 9
2 8
7 10

3

Actually the minimum here is 2: [0,4] covers 0–4; ... let's verify a clean example:

10 4
0 5
3 8
6 10
1 4

Sample Output:

2

(Selected: [0,5] and [3,8]... doesn't reach 10. Let's try [0,5] and [6,10] — gap at 5-6. Hmm. Use [0,5]+[3,8]+[6,10] = 3. Or with the fourth interval [1,4] added... minimum = 2: [0,5] ∪ [6,10] has a gap. Minimum = 3.)

Clean sample:

12 4
0 4
2 7
5 10
8 12

Sample Output:

3

(Selected: [0,4], [2,7], [8,12] — covers 0–4, 2–7, 8–12 with a gap at 7–8. Need [5,10] instead: [0,4]+[5,10]+[8,12] covers fully. Minimum = 3.)

Greedy strategy: Sort intervals by left endpoint ascending. Maintain covered = how far we've covered so far (initially 0). At each step, among all intervals with l[i] ≤ covered (they can extend our coverage), pick the one with the largest right endpoint (farthest). Advance covered to farthest and increment count.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T, n;
    cin >> T >> n;

    vector<pair<int,int>> intervals(n);
    for (auto &[l, r] : intervals) cin >> l >> r;

    sort(intervals.begin(), intervals.end());  // sort by left endpoint

    int covered = 0;    // currently covered up to 'covered'
    int count = 0;
    int i = 0;

    while (covered < T) {
        int farthest = covered;

        // Among all intervals with left endpoint <= covered, find the farthest right
        while (i < n && intervals[i].first <= covered) {
            farthest = max(farthest, intervals[i].second);
            i++;
        }

        if (farthest == covered) {
            // No interval can extend coverage — impossible
            cout << "Impossible\n";
            return 0;
        }

        covered = farthest;
        count++;
    }

    cout << count << "\n";
    return 0;
}
// Time complexity: O(N log N)

Step-by-step trace (T=12, intervals sorted: [0,4],[2,7],[5,10],[8,12]):

covered=0, count=0:
  Scan while l ≤ 0: [0,4] qualifies. farthest = max(0,4) = 4. i=1.
  Advance: covered=4, count=1.

covered=4, count=1:
  Scan while l ≤ 4: [2,7] (l=2≤4), [5,10] (l=5>4 STOP). farthest=max(4,7)=7. i=2.
  Advance: covered=7, count=2.

covered=7, count=2:
  Scan while l ≤ 7: [5,10] (l=5≤7), [8,12] (l=8>7 STOP). farthest=max(7,10)=10. i=3.
  Advance: covered=10, count=3.

covered=10, count=3:
  Scan while l ≤ 10: [8,12] (l=8≤10). farthest=max(10,12)=12. i=4.
  Advance: covered=12=T. count=4. Done.

Answer: 4

⚠️ Key difference from stabbing: Stabbing sorts by right endpoint (cover current interval as widely as possible). Covering sorts by left endpoint (always extend coverage from where we stopped, as far right as possible).

4.1.5 The Scheduling Problem: Minimize Lateness

Problem: You have one machine and N jobs. Job i has:

• Processing time t[i] — how long it takes to run.
• Deadline d[i] — the time by which it should ideally finish.

The machine runs jobs sequentially (no overlap, no idle time between jobs). The lateness of job i is max(0, finish_time[i] − d[i]) — how much it overshoots its deadline (0 if it finishes on time). Minimize the maximum lateness across all jobs.

Input format:

N
t[1] d[1]
t[2] d[2]
...
t[N] d[N]

Sample Input:

4
3 6
2 8
1 4
4 9

Sample Output:

1

Explanation: Sort by deadline ascending: job3(t=1,d=4), job1(t=3,d=6), job2(t=2,d=8), job4(t=4,d=9).

Job 3: runs [0,1],   finishes at 1.  lateness = max(0, 1-4)  = 0
Job 1: runs [1,4],   finishes at 4.  lateness = max(0, 4-6)  = 0
Job 2: runs [4,6],   finishes at 6.  lateness = max(0, 6-8)  = 0
Job 4: runs [6,10],  finishes at 10. lateness = max(0, 10-9) = 1
Maximum lateness = 1 ✓

Sample Input (no lateness possible):

3
3 6
2 9
1 4

Sample Output:

0

Sorted by deadline: job3(t=1,d=4), job1(t=3,d=6), job2(t=2,d=9)
Job 3: finishes at 1.  lateness = max(0, 1-4)  = 0
Job 1: finishes at 4.  lateness = max(0, 4-6)  = 0
Job 2: finishes at 6.  lateness = max(0, 6-9)  = 0
Maximum lateness = 0 ✓

Constraints: 1 <= N <= 10^5, 1 <= t[i] <= 10^4, 1 <= d[i] <= 10^9

Greedy Strategy: Earliest Deadline First (EDF)

Rule: Sort jobs by their deadline in ascending order. Run them in that order without any gaps.

Why EDF is optimal — the exchange argument:

Suppose the optimal schedule has two adjacent jobs A and B where d[A] > d[B] (A has a later deadline but runs first). Let S be the finish time of everything before A. Then:

Since d[A] > d[B], B is more urgent. In A→B order: B finishes at S + t[A] + t[B], which is the same as in B→A order — but B's deadline is earlier, making it potentially more late. Swapping to B→A never increases max lateness. Therefore, any non-EDF schedule can be improved or maintained by swapping, so EDF is optimal.

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

int main() {
    int n;
    cin >> n;

    vector<pair<int,int>> jobs(n);  // {deadline, processing_time}
    for (int i = 0; i < n; i++) cin >> jobs[i].second >> jobs[i].first;

    sort(jobs.begin(), jobs.end());  // sort by deadline

    int time = 0;
    int maxLateness = 0;

    for (auto [deadline, proc] : jobs) {
        time += proc;                          // finish time of this job
        int lateness = max(0, time - deadline); // how late is it?
        maxLateness = max(maxLateness, lateness);
    }

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

Proof sketch: If job A has earlier deadline than B but is scheduled after B, swap them. The lateness of A can only decrease (it finishes earlier), and the lateness of B can only increase by at most the processing time of A — but since d[A] ≤ d[B], B's lateness doesn't worsen. So EDF is optimal.

4.1.6 Huffman Coding (Greedy Tree Building)

Problem: You have N symbols, each appearing with frequency freq[i]. You want to assign each symbol a binary codeword (a string of 0s and 1s) such that no codeword is a prefix of another (prefix-free code). The total encoding cost = sum of freq[i] × depth[i] over all symbols, where depth[i] is the length of symbol i's codeword. Minimize this total cost.

This is equivalent to: build a binary tree where each symbol is a leaf, minimizing ∑ freq[i] × depth[i]. The total merge cost (sum of all internal node values) equals the total encoding cost.

Input format:

N
freq[1] freq[2] ... freq[N]

Sample Input:

5
5 9 12 13 16

Sample Output:

130

Trace:

Heap: {5, 9, 12, 13, 16}
Step 1: merge 5+9=14.    Heap: {12, 13, 14, 16}. cost=14
Step 2: merge 12+13=25.  Heap: {14, 16, 25}.     cost=14+25=39
Step 3: merge 14+16=30.  Heap: {25, 30}.          cost=39+30=69
Step 4: merge 25+30=55.  Heap: {55}.              cost=69+55=124
Output: 124

Canonical Sample Input:

4
1 2 3 4

Sample Output:

19

Step 1: merge 1+2=3.  Heap: {3, 3, 4}. cost=3
Step 2: merge 3+3=6.  Heap: {4, 6}.    cost=3+6=9
Step 3: merge 4+6=10. Heap: {10}.      cost=9+10=19 ✓

Constraints: 2 <= N <= 10^5, 1 <= freq[i] <= 10^9

Why Always Merge the Two Smallest?

Greedy insight: The two symbols with the lowest frequencies should be deepest in the tree (longest codewords), because longer codewords for rare symbols contribute less to total cost. By always merging the two current minimums, we ensure the heaviest-used symbols stay near the root.

Exchange argument: Suppose in an optimal tree, the two deepest leaves (at the same depth) are not the two smallest-frequency symbols. Swap them with the two smallest-frequency symbols. Since depth is the same and we've moved larger frequencies up and smaller ones down... wait, moving larger frequencies to deeper positions increases cost. So the two deepest leaves must be the smallest frequencies. The greedy rule follows directly.

The total cost identity: Each time we merge two nodes with costs a and b, we pay a + b. This cost is paid once for each "level" the merged node rises. The total merge cost equals the sum of all internal node values, which equals the total encoding length ∑ freq[i] × depth[i].

Practical application (USACO context): Huffman's algorithm appears in "minimum cost to combine N piles" problems. Any time you have N groups and must repeatedly merge two, paying the sum of the merged sizes, the answer is the sum of all merge operations — computed by Huffman's greedy.

Extended Sample:

Input:
6
3 1 1 2 5 4

Sorted: 1 1 2 3 4 5
Step 1: merge 1+1=2.  Heap: {2, 2, 3, 4, 5}. cost=2
Step 2: merge 2+2=4.  Heap: {3, 4, 4, 5}.    cost=2+4=6
Step 3: merge 3+4=7.  Heap: {4, 5, 7}.        cost=6+7=13
Step 4: merge 4+5=9.  Heap: {7, 9}.           cost=13+9=22
Step 5: merge 7+9=16. Heap: {16}.             cost=22+16=38
Output: 38

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

int main() {
    int n;
    cin >> n;

    priority_queue<long long, vector<long long>, greater<long long>> pq;  // min-heap
    for (int i = 0; i < n; i++) {
        long long f; cin >> f;
        pq.push(f);
    }

    long long totalCost = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        totalCost += a + b;  // cost of merging a and b
        pq.push(a + b);      // merged group has frequency a+b
    }

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

4.1.7 Permutation Greedy: Sorting by Custom Criteria

Permutation greedy covers a broad class of problems: given a set of elements, how should they be ordered to optimize some objective? The key is deriving the correct sort criterion, then proving it via an exchange argument.

Classic Problem 1: Minimize Total Completion Time (Shortest Job First)

Problem: You are given N jobs to be executed sequentially on a single machine. Job i has processing time t[i]. The completion time of job i is the total time elapsed from start until job i finishes. Minimize the sum of all completion times.

Input format:

N
t[1] t[2] ... t[N]

Sample Input:

3
3 1 2

Sample Output:

10

Greedy strategy: Sort by processing time in ascending order (Shortest Job First, SJF).

Why is SJF optimal? (Exchange argument)

Suppose the optimal ordering has two adjacent jobs A (processing time a) and B (processing time b) with a > b (B is shorter but comes after A). Let T be the cumulative completion time before these two jobs:

Since a > b, we have 2T + 2a + b > 2T + a + 2b, so B→A gives a smaller sum.

Therefore, any adjacent pair where a longer job precedes a shorter one can be improved by swapping. Repeating this until no such pair exists yields the optimal SJF order.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> t(n);
    for (int &x : t) cin >> x;

    sort(t.begin(), t.end());  // SJF: sort by processing time ascending

    long long totalCompletion = 0;
    long long curTime = 0;
    for (int i = 0; i < n; i++) {
        curTime += t[i];
        totalCompletion += curTime;
    }

    cout << totalCompletion << "\n";
    return 0;
}
// Time complexity: O(N log N)

Step-by-step trace:

Sorted t = [1, 2, 3]

i=0: curTime = 1,  totalCompletion = 1
i=1: curTime = 3,  totalCompletion = 4
i=2: curTime = 6,  totalCompletion = 10 ✓

Classic Problem 2: Largest Number (Concatenation Greedy)

Problem: Given a list of N non-negative integers, arrange them into a sequence and concatenate all their decimal representations to form the largest possible number. Output as a string (suppress leading zeros, but output "0" if all inputs are zero).

Input format:

N
a[1] a[2] ... a[N]

Sample Input:

5
3 30 34 5 9

Sample Output:

9534330

Sample Input 2:

3
0 0 0

Sample Output 2:

0

Greedy strategy: Define a custom comparator: for two numbers a and b (as strings), place a before b if str(a) + str(b) > str(b) + str(a).

Why does this comparator work? It defines a provably transitive total order. If ab > ba and bc > cb, then ac > ca follows algebraically (proof omitted).

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<string> nums(n);
    for (string &s : nums) cin >> s;

    // Custom sort: place a before b when a+b > b+a
    sort(nums.begin(), nums.end(), [](const string &a, const string &b) {
        return a + b > b + a;
    });

    // Edge case: all zeros
    if (nums[0] == "0") {
        cout << "0\n";
        return 0;
    }

    string result = "";
    for (const string &s : nums) result += s;
    cout << result << "\n";
    return 0;
}
// Time complexity: O(N log N · L), where L = max number of digits

Step-by-step trace:

nums = ["3", "30", "34", "5", "9"]

Compare selected pairs:
"3"+"30"="330" vs "30"+"3"="303"  →  "3" goes first
"9"+"5"="95"  vs "5"+"9"="59"    →  "9" goes first
"34"+"3"="343" vs "3"+"34"="334" →  "34" goes first

Sorted: ["9", "5", "34", "3", "30"]
Result: "9534330" ✓

⚠️ Warning: You cannot simply sort by numeric value! For example "3" > "30" numerically, but concatenation "330" > "303", so "3" should come first. Always use the concatenation comparator.

Classic Problem 3: Rearrange Arrays to Maximize (or Minimize) Dot Product

Problem: Given two arrays A[1..N] and B[1..N] of integers, you may rearrange each array independently in any order. Compute both the maximum and minimum possible values of ∑ A[i] × B[i] after rearrangement.

Input format:

N
A[1] A[2] ... A[N]
B[1] B[2] ... B[N]

Sample Input:

3
1 3 2
4 1 3

Sample Output:

Max: 19
Min: 13

Trace:

• Maximize: sort both ascending → A=[1,2,3], B=[1,3,4]. Sum = 1×1 + 2×3 + 3×4 = 19 ✓
• Minimize: sort A ascending, B descending → A=[1,2,3], B=[4,3,1]. Sum = 1×4 + 2×3 + 3×1 = 13 ✓

Greedy (maximize): Sort A ascending, sort B ascending (same direction) — "large pairs with large". Greedy (minimize): Sort A ascending, sort B descending (opposite) — "large pairs with small".

Exchange argument (maximize case): Suppose a₁ < a₂ but b₁ > b₂ (A and B paired in opposite order):

• Current: a₁b₁ + a₂b₂
• After swap: a₁b₂ + a₂b₁

Difference = (a₁b₁ + a₂b₂) - (a₁b₂ + a₂b₁) = (a₂ - a₁)(b₁ - b₂) > 0 (since a₂ > a₁, b₁ > b₂)

So same-direction pairing is always larger. This result is known as the Rearrangement Inequality.

// Maximize sum(A[i] * B[i])
sort(A.begin(), A.end());  // ascending
sort(B.begin(), B.end());  // ascending
long long maxSum = 0;
for (int i = 0; i < n; i++) maxSum += (long long)A[i] * B[i];

// Minimize sum(A[i] * B[i])
sort(A.begin(), A.end());                        // ascending
sort(B.begin(), B.end(), greater<int>());         // descending
long long minSum = 0;
for (int i = 0; i < n; i++) minSum += (long long)A[i] * B[i];

💡 Rearrangement Inequality mnemonic: Pairing "large with large, small with small" maximizes; pairing "large with small, small with large" minimizes.

4.1.8 Task Assignment: Two-Sequence Matching

Task assignment problems involve matching elements from two sorted sequences to optimize some objective. The key pattern: sort both sequences, then use a two-pointer scan or direct index pairing.

Classic Model: Minimize Total Waiting Time

Problem: N customers arrive at a service counter. Customer i requires s[i] time units of service. The server handles one customer at a time. Every customer pays for their waiting time (the time they stand in line before service begins). Choose the service order to minimize the total waiting time across all customers.

Input format:

N
s[1] s[2] ... s[N]

Sample Input:

4
4 2 1 3

Sample Output:

10

Trace (SJF order: 1, 2, 3, 4):

Customer 3 (s=1): wait=0,  service ends at 1.
Customer 2 (s=2): wait=1,  service ends at 3.
Customer 4 (s=3): wait=3,  service ends at 6.
Customer 1 (s=4): wait=6,  service ends at 10.
Total waiting time = 0+1+3+6 = 10 ✓

(This is identical to the SJF problem — sort by service time ascending.)

Key Model: Maximize Completed Tasks

Problem: You have N workers and N jobs. Worker i has ability ability[i]; job j has difficulty difficulty[j]. Worker i can complete job j only if ability[i] >= difficulty[j]. Each worker can do at most one job; each job requires at most one worker. Maximize the number of completed (worker, job) pairs.

Input format:

N
ability[1] ability[2] ... ability[N]
difficulty[1] difficulty[2] ... difficulty[N]

Sample Input:

5
3 1 5 2 4
2 4 6 1 3

Sample Output:

4

Trace: ability sorted=[1,2,3,4,5], difficulty sorted=[1,2,3,4,6].

i=0(ability=1), j=0(diff=1): 1>=1 → match. completed=1, i=1,j=1
i=1(ability=2), j=1(diff=2): 2>=2 → match. completed=2, i=2,j=2
i=2(ability=3), j=2(diff=3): 3>=3 → match. completed=3, i=3,j=3
i=3(ability=4), j=3(diff=4): 4>=4 → match. completed=4, i=4,j=4
i=4(ability=5), j=4(diff=6): 5<6  → skip worker. i=5 (exit)
Answer: 4 ✓

No-match example:

Input:  4 / 1 2 3 4 / 5 6 7 8
Output: 0   (no worker can do any job)

General case (arbitrary cost matrices): This is the Hungarian Algorithm (Assignment Problem), O(N³) — not solvable by greedy.

Special case (structured costs): When costs satisfy monotonicity, greedy works. Example: sort both arrays and match with two pointers.

Maximize completions (two-sequence greedy): Sort both arrays, then use two pointers.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> ability(n), difficulty(n);
    for (int &x : ability) cin >> x;
    for (int &x : difficulty) cin >> x;

    sort(ability.begin(), ability.end());
    sort(difficulty.begin(), difficulty.end());

    // Two pointers: greedily assign the weakest capable worker to each job
    int completed = 0;
    int i = 0, j = 0;  // i: worker pointer, j: job pointer

    while (i < n && j < n) {
        if (ability[i] >= difficulty[j]) {
            // Worker i can complete job j — match them
            completed++;
            i++;
            j++;
        } else {
            // Worker i is too weak — try the next stronger worker
            i++;
        }
    }

    cout << completed << "\n";
    return 0;
}
// Time complexity: O(N log N)

Why is this matching optimal? (Exchange argument)

Suppose in an optimal solution, a stronger worker A (a_A > a_B) is assigned an easier job (d_x < d_y), while weaker worker B takes the harder job (or no job). If a_B ≥ d_x, we can swap: B takes the easy job and A takes the hard one. The total completions don't decrease, and A has more remaining capacity — strictly better.

LeetCode 455: Assign Cookies (Classic Two-Sequence Greedy)

Problem: N children with greed factors g[i], M cookies with sizes s[i]. Cookie j satisfies child i iff s[j] ≥ g[i]. Each child gets at most one cookie. Maximize the number of satisfied children.

Greedy: Use the smallest sufficient cookie to satisfy the least greedy child (don't waste big cookies on small appetites).

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> g(n), s(m);
    for (int &x : g) cin >> x;
    for (int &x : s) cin >> x;

    sort(g.begin(), g.end());  // children: greed ascending
    sort(s.begin(), s.end());  // cookies: size ascending

    int satisfied = 0;
    int j = 0;  // cookie pointer

    for (int i = 0; i < n && j < m; ) {
        if (s[j] >= g[i]) {
            // Cookie j satisfies child i
            satisfied++;
            i++;
            j++;
        } else {
            // Cookie too small — try a bigger one
            j++;
        }
    }

    cout << satisfied << "\n";
    return 0;
}
// Time complexity: O(N log N + M log M)

Step-by-step trace:

g = [1, 2, 3] (greed),  s = [1, 1, 3, 4] (cookie sizes)
Both already sorted.

i=0(g=1), j=0(s=1): s[0]=1 >= g[0]=1 → satisfied! satisfied=1, i=1, j=1
i=1(g=2), j=1(s=1): s[1]=1 < g[1]=2  → j++, j=2
i=1(g=2), j=2(s=3): s[2]=3 >= g[1]=2 → satisfied! satisfied=2, i=2, j=3
i=2(g=3), j=3(s=4): s[3]=4 >= g[2]=3 → satisfied! satisfied=3, i=3 (exit)

Answer: 3 ✓ (all satisfied)

4.1.9 Interval Merging

Interval merging is another classic greedy type: merge all overlapping intervals into a set of non-overlapping intervals.

Problem: Given N intervals [l_i, r_i], merge all overlapping (or adjacent) intervals and output the resulting set.

Example:

Input:  [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Greedy algorithm:

1. Sort intervals by left endpoint ascending.
2. Maintain the current merged interval [curL, curR].
3. For each new interval [l, r]:
   • If l ≤ curR (overlap or adjacent): extend curR = max(curR, r)
   • Otherwise: finalize current merged interval, start a new one.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int,int>> intervals(n);
    for (auto &[l, r] : intervals) cin >> l >> r;

    sort(intervals.begin(), intervals.end());  // sort by left endpoint

    vector<pair<int,int>> merged;

    for (auto [l, r] : intervals) {
        if (merged.empty() || l > merged.back().second) {
            // No overlap — start a new merged interval
            merged.push_back({l, r});
        } else {
            // Overlap — extend the right endpoint
            merged.back().second = max(merged.back().second, r);
        }
    }

    cout << merged.size() << " merged intervals:\n";
    for (auto [l, r] : merged) {
        cout << "[" << l << "," << r << "] ";
    }
    cout << "\n";
    return 0;
}
// Time complexity: O(N log N)

Step-by-step trace:

Input (sorted): [1,3],[2,6],[8,10],[15,18]

[1,3]:  merged is empty → add directly.  merged=[[1,3]]
[2,6]:  2 <= 3 (overlap) → extend: [1, max(3,6)]=[1,6].  merged=[[1,6]]
[8,10]: 8 > 6 (no overlap) → add new.  merged=[[1,6],[8,10]]
[15,18]:15 > 10 (no overlap) → add new. merged=[[1,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]] ✓

Variant: Total Coverage Length

// Total length covered after merging
int totalLength = 0;
for (auto [l, r] : merged) totalLength += r - l;

Variant: Count Gaps Between Merged Intervals

// Number of gaps (uncovered segments) between merged intervals
int gaps = (int)merged.size() - 1;  // gaps between consecutive merged intervals
// Length of each gap:
for (int i = 1; i < (int)merged.size(); i++) {
    int gapLen = merged[i].first - merged[i-1].second;
    // process gapLen...
}

Variant: Minimum Intervals to Cover a Range

See §4.1.4 "Minimization: Minimum Intervals to Cover a Range".

Variant: Count Points Covered by At Least K Intervals

This is a sweep-line problem (not pure greedy):

// For each interval [l, r], add +1 at l and -1 at r+1
// Then prefix-sum to find coverage at each point
vector<pair<int,int>> events;
for (auto [l, r] : intervals) {
    events.push_back({l, +1});
    events.push_back({r + 1, -1});
}
sort(events.begin(), events.end());
int coverage = 0, maxCoverage = 0;
for (auto [pos, delta] : events) {
    coverage += delta;
    maxCoverage = max(maxCoverage, coverage);
}
// maxCoverage = maximum number of overlapping intervals at any point

Applications in USACO

Interval merging is a preprocessing tool that often appears in more complex USACO problems:

• Merging contiguous segments where cows stand on a number line
• Counting gaps between non-overlapping events
• Merging segments before applying further greedy operations
• USACO Bronze/Silver: "Fence painting" — merge painted segments, count total painted length
• USACO Silver: "Paired Up" — merge cow positions before greedy pairing

4.1.10 Greedy on Numbers and Strings

Number and string greedy typically involves "digit-by-digit construction": starting from the most significant position, make the locally optimal choice at each step.

Classic Problem 1: Remove K Digits to Get the Smallest Number

Problem: Given a string of digits (representing a large integer), remove exactly K digits (preserving the original order of remaining digits) to form the smallest possible integer.

Example:

"1432219", K=3  →  "1219"

Greedy idea: Maintain a monotone stack. Scan digits left to right:

• If the stack top > current digit AND we still have removals left: pop the stack top (remove the larger digit).
• Otherwise: push the current digit.
• If removals remain after scanning: remove from the right end of the stack.

Why remove larger digits? Digits to the left carry more weight. If a digit is larger than the one to its right, removing it makes the result smaller.

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

int main() {
    string num;
    int k;
    cin >> num >> k;

    string stk = "";  // use string as monotone stack

    for (char c : num) {
        // Pop stack top while it's larger than current digit and removals remain
        while (k > 0 && !stk.empty() && stk.back() > c) {
            stk.pop_back();
            k--;
        }
        stk.push_back(c);
    }

    // If removals remain, trim from the right
    stk.resize(stk.size() - k);

    // Remove leading zeros
    int start = 0;
    while (start < (int)stk.size() - 1 && stk[start] == '0') start++;

    cout << stk.substr(start) << "\n";
    return 0;
}
// Time complexity: O(N) — each digit is pushed/popped at most once

Step-by-step trace ("1432219", K=3):

stk="", k=3

'1': stack empty → push.  stk="1"
'4': 1 < 4 → push.        stk="14"
'3': 4 > 3 and k=3 → pop '4', k=2. 1 < 3 → push.  stk="13"
'2': 3 > 2 and k=2 → pop '3', k=1. 1 < 2 → push.  stk="12"
'2': 2 = 2 → push.        stk="122"
'1': 2 > 1 and k=1 → pop '2', k=0. push.  stk="121"
'9': k=0, no more removals → push.  stk="1219"

k=0, no trimming needed.  Result: "1219" ✓

Classic Problem 2: Jump Game II — Minimum Jumps

Problem: Given array A[0..n-1] where A[i] is the maximum jump length from position i. Starting at index 0, reach the last index in the minimum number of jumps.

Example:

A = [2, 3, 1, 1, 4]  →  2 jumps  (0→1→4)
A = [2, 3, 0, 1, 4]  →  2 jumps  (0→1→4)

Greedy idea: At each step, track the farthest position reachable within the current jump range. When you reach the end of the current range, you must jump — and you jump to the farthest position seen so far.

Think of it as "BFS layers": each jump is one layer. Within the current layer, scan all positions and find the farthest reachable next layer.

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

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    int jumps = 0;
    int curEnd = 0;    // end of current jump's reach
    int farthest = 0;  // farthest position reachable so far

    for (int i = 0; i < n - 1; i++) {
        farthest = max(farthest, i + A[i]);  // update farthest reachable
        if (i == curEnd) {                   // reached end of current jump range
            jumps++;
            curEnd = farthest;               // jump to farthest position
            if (curEnd >= n - 1) break;      // already can reach the end
        }
    }

    cout << jumps << "\n";
    return 0;
}
// Time complexity: O(N)

Step-by-step trace (A = [2,3,1,1,4]):

i=0: farthest=max(0,0+2)=2. i==curEnd(0) → jump! jumps=1, curEnd=2.
i=1: farthest=max(2,1+3)=4. i≠curEnd(2).
i=2: farthest=max(4,2+1)=4. i==curEnd(2) → jump! jumps=2, curEnd=4. 4≥4 → break.

Answer: 2 jumps ✓

Why is this greedy optimal? At each "forced jump" point (when you've exhausted the current range), you have no choice but to jump. The only question is where to land — and landing at the farthest reachable position maximizes the range for the next jump. Any other landing point gives a strictly smaller (or equal) range, which can only require more jumps.

Classic Problem 3: Best Time to Buy and Sell Stock (Greedy Version)

Problem: Given daily stock prices prices[0..n-1], you may buy and sell multiple times (but can only hold one share at a time). Maximize total profit.

Greedy idea: Whenever tomorrow's price is higher than today's, "buy today and sell tomorrow". Equivalently: accumulate every positive day-to-day difference.

Proof: For any continuously rising segment [a, b, c, d] with a < b < c < d:

• Single transaction: profit = d - a
• Daily trades: (b-a) + (c-b) + (d-c) = d - a (exactly the same!)

So collecting every upward increment is equivalent to any optimal multi-day strategy.

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

int main() {
    int n;
    cin >> n;
    vector<int> prices(n);
    for (int &x : prices) cin >> x;

    int profit = 0;
    for (int i = 1; i < n; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];  // capture every upward move
        }
    }

    cout << profit << "\n";
    return 0;
}
// Time complexity: O(N)

Step-by-step trace (prices = [7, 1, 5, 3, 6, 4]):

i=1: 1 < 7, no gain.      profit=0
i=2: 5 > 1, gain +4.      profit=4
i=3: 3 < 5, no gain.      profit=4
i=4: 6 > 3, gain +3.      profit=7
i=5: 4 < 6, no gain.      profit=7

Answer: 7 ✓ (Buy day 2 @ 1, sell day 3 @ 5; buy day 4 @ 3, sell day 5 @ 6)

⚠️ Note: This is the "unlimited transactions" version. "At most one transaction" → single pass tracking minimum buy price. "At most two/K transactions" → requires DP.

4.1.11 Regret Greedy

Regret greedy is the most powerful and most overlooked greedy technique. The core idea:

Make a greedy decision, but simultaneously preserve the ability to "undo" it — if the decision turns out to be suboptimal later, use a heap (priority queue) to reverse it in O(log N) time.

This makes some problems tractable that would otherwise seem unsolvable by greedy alone.

Classic Problem 1: Maximum Profit in K Operations (with Undo)

Problem: Given array A, each operation picks one element x (removing it from the array) for a gain of x. After each removal, the two adjacent elements in the original array merge into a new element (with value equal to their negated sum) and are placed back. Perform at most K operations to maximize total gain.

This is a variant of USACO 2016 January Platinum: Fort Moo, and the classic "odd-even cancellation" model.

Greedy + regret approach:

1. Maintain a max-heap.
2. Each step: take the heap top x (maximum gain), then insert -x (the "regret node" — undoing this operation costs -x).
3. If we later take -x from the heap, it means we "cancel" the previous operation. The net effect equals not having taken x, and instead taking the element that would have been available.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    priority_queue<long long> pq;  // max-heap
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        pq.push(x);
    }

    long long total = 0;
    for (int i = 0; i < k; i++) {
        long long top = pq.top(); pq.pop();
        if (top <= 0) break;  // taking this element would be a loss — stop
        total += top;
        pq.push(-top);        // insert regret node: cost to undo this operation
    }

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

The magic of regret: After taking x and inserting -x, suppose the next heap top is y. We can choose to:

• Take y (normal greedy)
• Take -x (equivalent to "cancel x, effectively replacing it with the next available element")

This automatically finds the optimal sequence of K choices across all possibilities.

Classic Problem 2: Minimize Makespan on K Machines (LPT)

Problem: N jobs with processing times t[i], K machines running in parallel (each machine handles one job at a time). Minimize the makespan (time when the last job finishes).

Greedy: Longest Processing Time First (LPT)

Sort jobs in descending order by processing time. Assign each job to the machine that finishes earliest (maintained with a min-heap).

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<int> t(n);
    for (int &x : t) cin >> x;

    sort(t.begin(), t.end(), greater<int>());  // descending: longest first

    // Min-heap: stores current finish time for each machine (initially all 0)
    priority_queue<long long, vector<long long>, greater<long long>> machines;
    for (int i = 0; i < k; i++) machines.push(0);

    for (int i = 0; i < n; i++) {
        long long earliest = machines.top(); machines.pop();
        machines.push(earliest + t[i]);  // assign job to the earliest-free machine
    }

    long long makespan = 0;
    while (!machines.empty()) {
        makespan = max(makespan, machines.top());
        machines.pop();
    }

    cout << makespan << "\n";
    return 0;
}
// Time complexity: O(N log N + N log K)

Step-by-step trace (t=[8,7,6,5,4,3,2,1], K=3):

Sorted descending: [8,7,6,5,4,3,2,1]. 3 machines start at: {0,0,0}

Assign 8 → machine with time 0:  finishes at  8. Heap: {0,0,8}
Assign 7 → machine with time 0:  finishes at  7. Heap: {0,7,8}
Assign 6 → machine with time 0:  finishes at  6. Heap: {6,7,8}
Assign 5 → machine at time 6:    finishes at 11. Heap: {7,8,11}
Assign 4 → machine at time 7:    finishes at 11. Heap: {8,11,11}
Assign 3 → machine at time 8:    finishes at 11. Heap: {11,11,11}
Assign 2 → machine at time 11:   finishes at 13. Heap: {11,11,13}
Assign 1 → machine at time 11:   finishes at 12. Heap: {11,12,13}

Makespan = 13 ✓

💡 LPT is not always optimal for general instances, but has a theoretical guarantee: LPT makespan ≤ (4/3 - 1/(3K)) × optimal. For exact optimal solutions at USACO Silver level, use binary search on the answer + greedy feasibility check.

Classic Problem 3: Job Sequencing with Deadlines

Problem: N jobs, each with a deadline d[i] (must be completed by day d[i], one job per day) and profit p[i]. Each job takes exactly 1 day. Maximize total profit.

Greedy approach:

1. Sort jobs by profit in descending order.
2. For each job, greedily assign it to the latest available time slot before its deadline (find it with reverse scan or Union-Find).

Simple version (O(N × D), D = max deadline):

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

int main() {
    int n;
    cin >> n;

    vector<pair<int,int>> jobs(n);  // {profit, deadline}
    for (auto &[p, d] : jobs) cin >> d >> p;

    sort(jobs.begin(), jobs.end(), greater<>());  // sort by profit descending

    int maxD = 0;
    for (auto [p, d] : jobs) maxD = max(maxD, d);

    vector<bool> slot(maxD + 1, false);  // slot[i] = true if day i is occupied
    long long totalProfit = 0;
    int count = 0;

    for (auto [p, d] : jobs) {
        // Search backwards from deadline for the latest free slot
        for (int t = d; t >= 1; t--) {
            if (!slot[t]) {
                slot[t] = true;
                totalProfit += p;
                count++;
                break;
            }
        }
    }

    cout << "Selected " << count << " jobs, total profit: " << totalProfit << "\n";
    return 0;
}
// Time complexity: O(N log N + N × D)
// Optimized to O(N log N) using Union-Find to track next free slot

Step-by-step trace:

Jobs: (d=2,p=100), (d=1,p=19), (d=2,p=27), (d=1,p=25), (d=3,p=15)
Sorted by profit: (100,d=2), (27,d=2), (25,d=1), (19,d=1), (15,d=3)

slot = [_, F, F, F]  (indices 1–3)

(100, d=2): search from d=2 → slot[2]=free → assign. slot=[_,F,T,F]. profit=100
(27,  d=2): search from d=2 → slot[2]=taken, slot[1]=free → assign. profit=127
(25,  d=1): search from d=1 → slot[1]=taken → no slot, skip.
(19,  d=1): search from d=1 → slot[1]=taken → no slot, skip.
(15,  d=3): search from d=3 → slot[3]=free → assign. profit=142

Result: 3 jobs selected, total profit = 142

4.1.12 Adversarial Matching

The classic "Tian Ji's Horse Racing" problem is the prototype for adversarial greedy matching: two parties each have N horses; you choose your order freely, the opponent's order is known. Maximize the number of races you win.

Strategy (two pointers, O(N)):

Sort your horses as A (ascending) and the opponent's as B (ascending).

• If your strongest horse A[hi] > opponent's strongest B[bhi] → beat their best with your best (win one race)
• If your strongest A[hi] ≤ opponent's strongest B[bhi] → sacrifice your weakest to exhaust their best (strategically lose, preserve your stronger horses)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> A(n), B(n);
    for (int &x : A) cin >> x;
    for (int &x : B) cin >> x;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    int wins = 0;
    int lo = 0, hi = n - 1;    // A's two pointers (weak end and strong end)
    int blo = 0, bhi = n - 1;  // B's two pointers

    while (lo <= hi) {
        if (A[hi] > B[bhi]) {
            // A's strongest beats B's strongest — win the race
            wins++;
            hi--;
            bhi--;
        } else {
            // A's strongest can't beat B's strongest — sacrifice A's weakest
            lo++;
            bhi--;
        }
    }

    cout << wins << "\n";
    return 0;
}
// Time complexity: O(N log N)

Step-by-step trace (A=[1,3,5], B=[2,4,6]):

A sorted: [1,3,5],  B sorted: [2,4,6]
lo=0, hi=2, bhi=2

Round 1: A[2]=5 vs B[2]=6: 5 ≤ 6 → sacrifice A's weakest (1) to lose against B's strongest (6). lo=1, bhi=1. wins=0
Round 2: A[2]=5 vs B[1]=4: 5 > 4  → A's strongest beats B's current strongest. hi=1, bhi=0. wins=1
Round 3: A[1]=3 vs B[0]=2: 3 > 2  → A's strongest beats B's current strongest. hi=0, bhi=-1. wins=2

Answer: wins=2 ✓  (A wins: 5 beats 4, 3 beats 2;  1 loses to 6)

Exchange argument: why is this strategy optimal?

• If A's strongest can beat B's strongest: using A's strongest on a weaker opponent means B's strongest must be faced by one of A's weaker horses — strictly worse. So beat the best with the best.
• If A's strongest cannot beat B's strongest: no horse from A can beat B's strongest, so use A's weakest to "burn" it (keep stronger horses for beatable opponents).

Variant: Adversarial Matching in USACO

Many USACO pairing/competition problems follow similar logic. For example:

Problem: A and B each have N values. Each round, both reveal one value; A[i] > B[j] means A scores 1, otherwise B scores (ties go to B). Both play optimally. How many points can A score at most?

(When both players know the full hand, this becomes game theory — more complex than single-player greedy.)

4.1.13 Prefix / Suffix Greedy and Bitwise Greedy

Prefix / Suffix Greedy

Many problems can be solved by making one greedy pass from the left (prefix) and one from the right (suffix), then combining the results.

Classic application: Best time to buy and sell stock (single transaction)

// At most one transaction, maximize profit
int n;
cin >> n;
vector<int> prices(n);
for (int &x : prices) cin >> x;

// prefix_min[i] = minimum of prices[0..i]  (best buy price so far)
// suffix_max[i] = maximum of prices[i..n-1] (best sell price from here)
vector<int> prefix_min(n), suffix_max(n);

prefix_min[0] = prices[0];
for (int i = 1; i < n; i++)
    prefix_min[i] = min(prefix_min[i-1], prices[i]);

suffix_max[n-1] = prices[n-1];
for (int i = n-2; i >= 0; i--)
    suffix_max[i] = max(suffix_max[i+1], prices[i]);

int maxProfit = 0;
for (int i = 0; i < n-1; i++)
    maxProfit = max(maxProfit, suffix_max[i+1] - prefix_min[i]);

cout << maxProfit << "\n";
// Time complexity: O(N)

Simpler one-pass version (only needs prefix minimum):

int minPrice = INT_MAX, maxProfit = 0;
for (int p : prices) {
    maxProfit = max(maxProfit, p - minPrice);
    minPrice = min(minPrice, p);
}

Classic: Distribute Candies (Two-Pass Greedy)

Problem (LeetCode 135 Candy): N children stand in a line, each with a rating rating[i]. Rules:

1. Each child must receive at least 1 candy.
2. A child with a higher rating than their neighbor must receive more candies than that neighbor.

Find the minimum total number of candies.

Two-pass greedy (prefix + suffix):

• First pass (left → right): if rating[i] > rating[i-1], then candy[i] = candy[i-1] + 1, else candy[i] = 1
• Second pass (right → left): if rating[i] > rating[i+1], then candy[i] = max(candy[i], candy[i+1] + 1)

Two passes ensure both left-neighbor and right-neighbor constraints are satisfied.

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

int main() {
    int n;
    cin >> n;
    vector<int> rating(n);
    for (int &x : rating) cin >> x;

    vector<int> candy(n, 1);  // everyone gets at least 1

    // First pass: satisfy "if higher than left neighbor, get more than left"
    for (int i = 1; i < n; i++) {
        if (rating[i] > rating[i - 1])
            candy[i] = candy[i - 1] + 1;
    }

    // Second pass: satisfy "if higher than right neighbor, get more than right"
    for (int i = n - 2; i >= 0; i--) {
        if (rating[i] > rating[i + 1])
            candy[i] = max(candy[i], candy[i + 1] + 1);
    }

    cout << accumulate(candy.begin(), candy.end(), 0) << "\n";
    return 0;
}
// Time complexity: O(N)

Step-by-step trace (rating = [1, 0, 2]):

Initial: candy = [1, 1, 1]

First pass (left → right):
  i=1: rating[1]=0 < rating[0]=1 → candy[1]=1 (unchanged)
  i=2: rating[2]=2 > rating[1]=0 → candy[2]=candy[1]+1=2
  candy = [1, 1, 2]

Second pass (right → left):
  i=1: rating[1]=0 < rating[2]=2 → unchanged
  i=0: rating[0]=1 > rating[1]=0 → candy[0]=max(1, candy[1]+1)=2
  candy = [2, 1, 2]

Total candies = 2+1+2 = 5 ✓

Why two passes are sufficient: The first pass handles "each child with a higher rating than their left neighbor". The second pass handles "each child with a higher rating than their right neighbor". Taking the max ensures the stricter of the two constraints is always met.

Bitwise Greedy

Classic: Construct maximum / minimum value bit by bit

The most common bitwise greedy pattern:

Problem: Given N numbers, select two to maximize their XOR.

Greedy (Trie): Insert all numbers into a binary Trie. For each number x, greedily walk the "opposite" branch at each bit level (from high to low), maximizing the XOR bit by bit.

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

const int MAXBIT = 30;

struct Trie {
    int ch[2];
    Trie() { ch[0] = ch[1] = -1; }
};

vector<Trie> trie(1);

void insert(int x) {
    int node = 0;
    for (int i = MAXBIT; i >= 0; i--) {
        int bit = (x >> i) & 1;
        if (trie[node].ch[bit] == -1) {
            trie[node].ch[bit] = trie.size();
            trie.push_back(Trie());
        }
        node = trie[node].ch[bit];
    }
}

int maxXOR(int x) {
    int node = 0, res = 0;
    for (int i = MAXBIT; i >= 0; i--) {
        int bit = (x >> i) & 1;
        int want = 1 - bit;  // greedy: try the opposite bit to make XOR = 1 here
        if (trie[node].ch[want] != -1) {
            res |= (1 << i);
            node = trie[node].ch[want];
        } else {
            node = trie[node].ch[bit];
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int &x : nums) cin >> x;

    for (int x : nums) insert(x);

    int ans = 0;
    for (int x : nums) ans = max(ans, maxXOR(x));

    cout << ans << "\n";
    return 0;
}
// Time complexity: O(N × MAXBIT) = O(32N)

Step-by-step trace (nums=[3,10,5,25,2,8], expected answer 28):

25 = 11001,  5 = 00101
XOR = 11100 = 28 ✓

Greedy query for x=5=00101 in the Trie:
  bit4: x's bit=0, want=1 → found 25's bit=1 → XOR bit4=1, res grows
  bit3: x's bit=0, want=1 → found 25's bit=1 → res grows
  ...  final: 5 XOR 25 = 28

💡 General bitwise greedy pattern: Process bits from highest to lowest. At each bit, greedily choose the branch that makes the result's bit equal to 1 (or 0, depending on the objective). A Trie supports each query in O(MAXBIT) time.

⚠️ Common Mistakes in Chapter 4.1

1. Applying greedy to DP problems: Just because greedy is simpler doesn't mean it's correct. Always test your greedy on small counterexamples. Coin change with arbitrary denominations is a classic trap.

2. Wrong sort criterion: Sorting by start time instead of end time for activity selection is a classic bug. The justification for WHY we sort a certain way (the exchange argument) is what tells you the correct criterion.

3. Off-by-one in overlap check: s >= lastEnd (allows adjacent activities) vs. s > lastEnd (requires a gap). Check which interpretation the problem intends.

4. Assuming greedy works without proof: Always verify with a small example or brief exchange argument. If you can't find a counterexample AND you can sketch why the greedy choice is "safe," it's likely correct.

5. Forgetting to sort: Greedy algorithms almost always begin with a sort. Forgetting to sort means the greedy "order" doesn't exist.

6. Integer overflow in comparators: When sorting by ratio w/t, avoid floating-point comparisons. Use cross-multiplication: w_A * t_B > w_B * t_A. Always cast to long long before multiplying.

   // ❌ Wrong: floating-point precision issues
   sort(jobs.begin(), jobs.end(), [](auto &a, auto &b) {
       return (double)a.w / a.t > (double)b.w / b.t;
   });
   // ✅ Correct: integer cross-multiplication
   sort(jobs.begin(), jobs.end(), [](auto &a, auto &b) {
       return (long long)a.w * b.t > (long long)b.w * a.t;
   });
   

7. Greedy on the wrong subproblem: Some problems look like "pick the best element each time" but the "best" depends on future context. If your greedy choice at step i changes what's optimal at step i+1, you likely need DP.

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: How do I tell if a problem can be solved greedily?

A: Three signals: ① After sorting, there's a clear processing order; ② You can use an exchange argument to show the greedy choice is never worse than any alternative; ③ You can't find a counterexample. If you find one (e.g., coin change with {1,5,6,9}), greedy fails — use DP instead.

Q2: What's the real difference between greedy and DP?

A: Greedy makes the locally optimal choice at each step and never looks back. DP considers all possible choices and builds the global optimum from subproblem solutions. Greedy is a special case of DP — it works when the local optimum happens to equal the global optimum.

Q3: What is the "binary search on answer + greedy check" pattern?

A: When a problem asks to "minimize the maximum" or "maximize the minimum," binary search on the answer X and use a greedy check(X) to verify feasibility. See the Convention problem in Chapter 4.2.

Q4: Why sort Activity Selection by end time instead of start time?

A: Sorting by end time ensures we always pick the activity that "frees up resources" earliest, leaving the most room for future activities. Sorting by start time might select an activity that starts early but ends very late, blocking all subsequent ones.

Q5: When should I use regret greedy instead of plain greedy?

A: Use regret greedy when: ① the problem allows at most K operations and K is small; ② each operation can be "undone" by a reverse operation; ③ plain greedy gives a suboptimal answer because early choices block better later ones. The key insight is that inserting a -x regret node into the heap lets you implicitly undo any previous choice in O(log N).

Q6: How do I handle ties in greedy sort criteria?

A: Ties usually don't matter for correctness (any tie-breaking order gives the same optimal value), but they can matter for implementation. When in doubt, add a secondary sort key that makes the order deterministic. For the "largest number" problem (§4.1.7), the comparator a+b > b+a handles ties correctly by definition.

Q7: My greedy passes all sample cases but fails on the judge. What's wrong?

A: Common culprits: ① Wrong sort criterion (e.g., sorting by start time instead of end time); ② Off-by-one in overlap check (>= vs >); ③ Integer overflow (use long long for products); ④ The problem actually requires DP — try to find a counterexample for your greedy rule.

🔗 Connections to Other Chapters

• Chapters 6.1–6.3 (DP) are the "upgrade" of greedy — when greedy fails, DP considers all choices
• Chapter 3.3 (Sorting & Binary Search) is the prerequisite — almost every greedy algorithm starts with a sort
• Chapter 4.2 applies greedy to real USACO problems, showcasing the classic "binary search on answer + greedy check" pattern
• Chapter 5.3 (Kruskal's MST) is fundamentally greedy — sort edges and greedily pick the minimum, one of the most classic greedy algorithms
• §4.1.7 Permutation Greedy — the Rearrangement Inequality and SJF are core tools for scheduling problems in USACO Silver
• §4.1.8 Two-Sequence Matching — the two-pointer pairing pattern appears frequently in USACO Bronze/Silver task assignment and cookie distribution problems
• §4.1.10 Monotone Stack Greedy — will be revisited and deepened in the Data Structures section (Part 3)

What comes next:

Chapter 4.1 (Greedy Fundamentals)  ←  You are here
        ↓
Chapter 4.2 (Greedy in USACO)      ←  Apply greedy to real contest problems
        ↓
Chapter 6.1–6.3 (Dynamic Programming)  ←  When greedy isn't enough
        ↓
Chapter 5.3 (Minimum Spanning Tree)    ←  Greedy on graphs (Kruskal)

Practice Problems

🎯 How to use these problems:

• First pass: Try each problem on your own for 20–30 minutes before reading the hint.
• Stuck? Open the 💡 Hint — it tells you the key insight without giving away the code.
• After solving: Compare your solution with the ✅ Full Solution. Look for differences in edge case handling and code style.
• Difficulty guide: 🟢 Easy (warm-up), 🟡 Medium (core skill), 🔴 Hard (contest-level)

Problem 4.1.1 — Meeting Rooms II 🟡 Medium

Problem: N meetings, each with a start time start[i] and end time end[i]. Find the minimum number of meeting rooms needed so all meetings can run without any overlap.

Input format:

3
0 30
5 10
15 20

Output: 2

Meetings (sorted by start): [0,30], [5,10], [15,20]

[0,30]:  heap empty → new room.       heap: {30}
[5,10]:  heap top=30 > 5 → new room.  heap: {10, 30}
[15,20]: heap top=10 ≤ 15 → reuse. pop 10, push 20.  heap: {20, 30}

Final heap size = 2 → Answer: 2

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int,int>> meetings(n);
    for (int i = 0; i < n; i++)
        cin >> meetings[i].first >> meetings[i].second;

    // Sort by start time
    sort(meetings.begin(), meetings.end());

    // Min-heap: stores end time of each active room
    priority_queue<int, vector<int>, greater<int>> pq;

    for (auto [start, end] : meetings) {
        if (!pq.empty() && pq.top() <= start) {
            // Reuse the earliest-free room
            pq.pop();
        }
        pq.push(end);  // This room is occupied until 'end'
    }

    cout << pq.size() << "\n";
    return 0;
}
// Time complexity: O(N log N)
// Space complexity: O(N)

Problem 4.1.2 — Gas Station 🔴 Hard

Problem: N gas stations arranged in a circle. Station i has gas[i] liters of gas; it costs cost[i] liters to travel from station i to station i+1. Your tank starts empty and has unlimited capacity. Can you complete the full circuit? If yes, output the starting station index (the solution is unique).

Example:

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]

Output: 3 (starting from station 3 completes the circuit)

gas  = [1, 2, 3, 4, 5],  cost = [3, 4, 5, 1, 2]
net gain = [-2, -2, -2, 3, 3]

start=0, tank=0, totalTank=0

i=0: tank = 0 + (1-3) = -2 < 0 → reset start=1, tank=0. totalTank=-2
i=1: tank = 0 + (2-4) = -2 < 0 → reset start=2, tank=0. totalTank=-4
i=2: tank = 0 + (3-5) = -2 < 0 → reset start=3, tank=0. totalTank=-6
i=3: tank = 0 + (4-1) =  3 ≥ 0 → keep.              totalTank=-3
i=4: tank = 3 + (5-2) =  6 ≥ 0 → keep.              totalTank=0

totalTank=0 ≥ 0 → solution exists. Answer: start = 3

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> gas(n), cost(n);
    for (int &x : gas) cin >> x;
    for (int &x : cost) cin >> x;

    int totalTank = 0;  // total net gas (determines feasibility)
    int tank = 0;       // current tank from 'start'
    int start = 0;      // current candidate starting station

    for (int i = 0; i < n; i++) {
        int gain = gas[i] - cost[i];
        tank += gain;
        totalTank += gain;

        if (tank < 0) {
            // Cannot reach i+1 from 'start' — reset
            start = i + 1;
            tank = 0;
        }
    }

    if (totalTank < 0) {
        cout << -1 << "\n";  // no solution
    } else {
        cout << start << "\n";
    }
    return 0;
}
// Time complexity: O(N) — single pass

Problem 4.1.3 — Minimum Platforms 🟡 Medium

Problem: N trains, each with an arrival time arr[i] and departure time dep[i]. If a train arrives when all platforms are occupied, it must wait. Find the minimum number of platforms so no train ever has to wait.

Example:

arr = [9:00, 9:40, 9:50, 11:00, 15:00, 18:00]
dep = [9:10, 12:00, 11:20, 11:30, 19:00, 20:00]

Output: 3

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int,int>> events;  // {time, type}: type=0 departure, type=1 arrival
    for (int i = 0; i < n; i++) {
        int a, d;
        cin >> a >> d;
        events.push_back({a, 1});   // arrival
        events.push_back({d, 0});   // departure (type=0 < 1, so departures sort first at same time)
    }

    sort(events.begin(), events.end());

    int platforms = 0, maxPlatforms = 0;
    for (auto [time, type] : events) {
        if (type == 1) platforms++;   // train arrives
        else platforms--;             // train departs
        maxPlatforms = max(maxPlatforms, platforms);
    }

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

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

int main() {
    int n;
    cin >> n;

    vector<int> arr(n), dep(n);
    for (int &x : arr) cin >> x;
    for (int &x : dep) cin >> x;

    sort(arr.begin(), arr.end());
    sort(dep.begin(), dep.end());

    int platforms = 1, maxPlatforms = 1;
    int i = 1, j = 0;  // i: next arrival, j: next departure

    while (i < n && j < n) {
        if (arr[i] <= dep[j]) {
            // Next arrival comes before next departure → need one more platform
            platforms++;
            i++;
        } else {
            // A train departs first → one platform freed
            platforms--;
            j++;
        }
        maxPlatforms = max(maxPlatforms, platforms);
    }

    cout << maxPlatforms << "\n";
    return 0;
}
// Time complexity: O(N log N)

arr sorted (minutes): [540, 580, 590, 660, 900, 1080]
dep sorted (minutes): [550, 690, 720, 750, 1140, 1200]

Initial: platforms=1, maxPlatforms=1, i=1, j=0

arr[1]=580 ≤ dep[0]=550? NO  → depart, platforms=0, j=1
arr[1]=580 ≤ dep[1]=690? YES → arrive, platforms=1, i=2
arr[2]=590 ≤ dep[1]=690? YES → arrive, platforms=2, i=3
arr[3]=660 ≤ dep[1]=690? YES → arrive, platforms=3 ← peak!, i=4
arr[4]=900 ≤ dep[1]=690? NO  → depart, platforms=2, j=2
...
Answer: maxPlatforms = 3 ✓

Problem 4.1.4 — Fractional Knapsack 🟢 Easy

Problem: N items, item i has weight w[i] and value v[i]. Knapsack capacity W. You may take any fraction of each item. Maximize total value.

Example:

N=3, W=50
Items: (w=10, v=60), (w=20, v=100), (w=30, v=120)

Output: 240.0

Sorted by unit value (v/w):
  Item 1: 60/10  = 6.0  ← highest
  Item 2: 100/20 = 5.0
  Item 3: 120/30 = 4.0

Remaining capacity W=50:
Take item 1 in full (10 kg) → value += 60,  W=40
Take item 2 in full (20 kg) → value += 100, W=20
Take 20/30 of item 3        → value += 80,  W=0

Total value = 60 + 100 + 80 = 240 ✓

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    double W;
    cin >> n >> W;

    vector<pair<double,double>> items(n);  // {value, weight}
    for (int i = 0; i < n; i++)
        cin >> items[i].second >> items[i].first;

    // Sort by unit value (v/w) descending
    sort(items.begin(), items.end(), [](const auto &a, const auto &b) {
        return a.first / a.second > b.first / b.second;
    });

    double totalValue = 0.0;
    double remaining = W;

    for (auto [v, w] : items) {
        if (remaining <= 0) break;
        if (w <= remaining) {
            // Take the whole item
            totalValue += v;
            remaining -= w;
        } else {
            // Take a fraction
            totalValue += v * (remaining / w);
            remaining = 0;
        }
    }

    cout << fixed << setprecision(2) << totalValue << "\n";
    return 0;
}
// Time complexity: O(N log N)

Problem 4.1.5 — Jump Game 🟡 Medium

Problem: Given an array A of non-negative integers, starting at index 0, at position i you can jump up to A[i] steps forward. Determine whether you can reach the last index (n-1).

Examples:

A = [2, 3, 1, 1, 4] → true  (0→1→4)
A = [3, 2, 1, 0, 4] → false (cannot pass position 3)

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

bool canJump(vector<int>& A) {
    int n = A.size();
    int farthest = 0;  // farthest reachable index

    for (int i = 0; i < n; i++) {
        if (i > farthest) return false;  // position i is unreachable
        farthest = max(farthest, i + A[i]);
        if (farthest >= n - 1) return true;  // end is reachable
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;
    cout << (canJump(A) ? "true" : "false") << "\n";
}

// Minimum jumps to reach the end — greedy, O(N)
int jump(vector<int>& A) {
    int n = A.size();
    int jumps = 0;
    int curEnd = 0;    // farthest position reachable in the current jump
    int farthest = 0;  // farthest position reachable in the next jump

    for (int i = 0; i < n - 1; i++) {
        farthest = max(farthest, i + A[i]);
        if (i == curEnd) {
            // Must jump here — we've reached the boundary of the current jump
            jumps++;
            curEnd = farthest;
        }
    }
    return jumps;
}

i=0: farthest = max(0, 0+2) = 2
i=1: farthest = max(2, 1+3) = 4 ≥ n-1=4 → return true ✓

Trace for A = [3,2,1,0,4]:
i=0: farthest = max(0, 0+3) = 3
i=1: farthest = max(3, 1+2) = 3
i=2: farthest = max(3, 2+1) = 3
i=3: farthest = max(3, 3+0) = 3
i=4: 4 > farthest=3 → return false ✓

🏆 Challenge Problem: USACO 2016 February Silver — Fencing the Cows (Interval Stabbing)

Problem: Farmer John has N fence segments on the number line, each defined as [L_i, R_i]. Find the minimum number of "anchor points" such that every fence segment contains at least one anchor point (the interval stabbing problem).

Segments: [1,4], [2,6], [3,5], [7,9], [8,10]
Sorted by right endpoint: [1,4], [3,5], [2,6], [7,9], [8,10]

lastPoint=-inf:
[1,4]:  lastPoint=-inf < 1 → place anchor at 4. lastPoint=4. count=1
[3,5]:  3 ≤ lastPoint=4 ≤ 5 → covered, skip.
[2,6]:  2 ≤ lastPoint=4 ≤ 6 → covered, skip.
[7,9]:  lastPoint=4 < 7 → place anchor at 9. lastPoint=9. count=2
[8,10]: 8 ≤ lastPoint=9 ≤ 10 → covered, skip.

Answer: 2 anchor points

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<int,int>> segs(n);  // {right, left}
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        segs[i] = {r, l};
    }

    sort(segs.begin(), segs.end());  // sort by right endpoint

    int count = 0;
    long long lastPoint = LLONG_MIN;

    for (auto [r, l] : segs) {
        if (lastPoint < l) {
            // Current anchor does not cover this segment — place a new one
            lastPoint = r;   // place at right end to cover as many future segments as possible
            count++;
        }
    }

    cout << count << "\n";
    return 0;
}
// Time complexity: O(N log N)