Chapter 4.2: Greedy in USACO

USACO problems that yield to greedy solutions are some of the most satisfying to solve — once you see the insight, the code practically writes itself. This chapter walks through several USACO-style problems where greedy is the key.

4.2.1 Pattern Recognition: Is It Greedy?

Recognizing a greedy problem is the hardest part — it looks like DP, it smells like DP, but it has a special structure that lets you make decisions locally. Here is a practical framework.

The Three-Question Test

Before coding, ask yourself:

1. Can I sort the input in some clever way? Most greedy algorithms begin with a sort. If you can identify a natural ordering (by deadline, by end time, by ratio, by custom comparator), you're likely on a greedy track.

2. Is there a "natural" greedy choice at each step? Can you always identify one element/decision that is clearly "best right now," and argue that taking it never closes off better future options?

3. Can you construct an exchange argument? If any two adjacent choices are "out of greedy order," can you swap them without making the solution worse? If yes, by bubble-sort reasoning, the greedy order is optimal.

If yes to all three → try greedy. If you find a counterexample → switch to DP.

USACO Greedy Pattern Taxonomy

Understanding which pattern a problem falls into is often the key insight:

Red Flags: When Greedy Fails

Watch out for these signs that greedy won't work:

• Items/choices have weights: If selecting one item excludes multiple others with different combined values, greedy tends to fail. Use DP. (0/1 Knapsack, Weighted Interval Scheduling)
• Decisions interact non-locally: If choosing element i now affects which elements are available two steps later in a non-trivial way. (Longest Increasing Subsequence — greedy gives wrong answer)
• You can find a 3-element counterexample: Always test on tiny inputs: N=2 and N=3. If N=3 breaks your greedy, it's wrong.

⚠️ USACO contest tip: Greedy problems at Silver/Gold level almost always require a proof sketch — either an exchange argument or a mono-tonicity argument for binary search. If you can't sketch why greedy works in 2 sentences, be more cautious.

If yes to any of these, try greedy. If your greedy fails a test case, reconsider — maybe it's actually a DP problem.

4.2.2 USACO Bronze: Cow Sorting

Problem: You have N cows standing in a line. Cow i has a "grumpiness" value g[i]. You want to sort the line so that grumpiness values are in strictly increasing order. The only allowed operation is to swap two adjacent cows. When you swap cows at positions i and j (adjacent), you pay a cost of g[i] + g[j]. Find the minimum total cost to sort the line.

Input format:

N
g[1] g[2] ... g[N]

Sample Input:

3
3 1 2

Sample Output:

9

Sample Input 2:

5
5 4 3 2 1

Sample Output 2:

60

Step-by-step trace for [5,4,3,2,1]: All C(5,2)=10 pairs are inversions.

(5,4):9  (5,3):8  (5,2):7  (5,1):6
(4,3):7  (4,2):6  (4,1):5
(3,2):5  (3,1):4
(2,1):3
Total = 9+8+7+6+7+6+5+5+4+3 = 60 ✓

Counting inversions in O(N²):

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

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

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

    // Total cost = sum of (g[i] + g[j]) for every inversion pair i < j where g[i] > g[j]
    // Equivalently: for each element g[i], add g[i] * (# elements it must "cross"):
    //   (# elements to its left that are > g[i]) + (# elements to its right that are < g[i])
    // Both counts together = total inversions involving g[i].

    long long totalCost = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (g[i] > g[j]) {
                totalCost += g[i] + g[j];  // this inversion costs g[i]+g[j]
            }
        }
    }

    cout << totalCost << "\n";
    return 0;
}
// Time: O(N²) — for N ≤ 10^5 use merge-sort inversion count (O(N log N))

Example:

Input: g = [3, 1, 2]
Inversions: (3,1) → cost 4; (3,2) → cost 5
Total: 9

Verification: Bubble sort on [3,1,2]:

• Swap(3,1) = cost 4 → [1,3,2]
• Swap(3,2) = cost 5 → [1,2,3]
• Total = 9 ✓

4.2.3 USACO Bronze: The Cow Signal (Greedy Simulation)

Many USACO Bronze problems are pure simulation with a greedy twist: process events in time order and greedily maintain the optimal state at each step. The key is identifying what to simulate and in what order.

Problem: N cows each want to leave the barn and reach the pasture. Cow i is ready to leave at time t[i]. The road between barn and pasture can hold at most C cows simultaneously; transit takes exactly 1 time unit. Cows must wait at the barn if the road is full. Assuming we send cows as early as possible, what is the time when the last cow arrives?

Input format:

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

Sample Input:

6 3
1 3 5 2 4 6

Sample Output:

7

Constraints: 1 ≤ N ≤ 10^5, 1 ≤ C ≤ N, 1 ≤ t[i] ≤ 10^9

Greedy key insight: Sort cows by departure time. Then greedily send the next available batch of C cows as soon as the road clears. The last cow's arrival = the departure time of the last batch + 1 (transit time).

Trace for sample (sorted t=[1,2,3,4,5,6], C=3):

Batch 1: cows with t=1,2,3.  Road free at time 0.  Depart = max(0, t[0]=1) = 1.  Arrive = 2.
Batch 2: cows with t=4,5,6.  Road free at time 2.  Depart = max(2, t[3]=4) = 4.  Arrive = 5.
Last arrival = 5.

(Actual output depends on exact problem interpretation; the pattern above is the standard approach.)

Simplified implementation for batch-departure model:

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

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

    int n, c;
    cin >> n >> c;

    vector<int> t(n);
    for (int &x : t) cin >> x;
    sort(t.begin(), t.end());  // process cows in order of departure time

    int ans = 0;
    // Process in groups of c
    for (int i = 0; i < n; i += c) {
        // Group starts at t[i] (the earliest cow in this batch)
        // But batch can't start before previous batch finished
        ans = max(ans, t[i]);  // this batch must start at least when earliest cow is ready
        ans++;  // takes 1 time unit
    }

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

4.2.4 USACO Silver: Paired Up

Problem: You have N cows in group A and N cows in group B. You must pair each cow in A with exactly one cow in B (one-to-one). The profit of pairing cow a from group A with cow b from group B is min(a, b). Maximize the total profit across all N pairs.

Input format:

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

Sample Input:

3
1 3 5
2 4 6

Sample Output:

9

Trace (sort both ascending, pair by index):

A sorted: [1, 3, 5]
B sorted: [2, 4, 6]

Pair (1,2): min=1
Pair (3,4): min=3
Pair (5,6): min=5
Total = 1+3+5 = 9 ✓

Sample Input 2:

3
5 1 3
4 6 2

Sample Output 2:

9

(Same as before — the input order doesn't matter, only the values.)

Constraints: 1 ≤ N ≤ 10^5, 1 ≤ A[i], B[i] ≤ 10^9

Why sort both the same way? Exchange argument: suppose in some pairing, we have a₁ < a₂ paired with b₁ > b₂ (A sorted ascending but B not). Then:

Current:  min(a₁,b₁) + min(a₂,b₂)
Swapped:  min(a₁,b₂) + min(a₂,b₁)

Since a₁ < a₂ and b₁ > b₂:

• If a₂ ≤ b₂: current = a₁ + a₂, swapped = a₁ + a₂. (Equal)
• If a₁ ≤ b₂ < a₂: current = a₁ + b₂, swapped = a₁ + a₂ ≥ current. (Swap is better)
• More cases follow, but the conclusion is: same-direction pairing (both sorted ascending) achieves the maximum.

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

int main() {
    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());

    long long total = 0;
    for (int i = 0; i < n; i++) {
        total += min(A[i], B[i]);  // pair i-th smallest with i-th smallest
    }

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

This works because if you pair (a_large, b_small) instead of (a_large, b_large) and (a_small, b_small), you get min(a_large, b_small) + min(a_small, b_small) ≤ min(a_large, b_large) + min(a_small, b_small). Always match sorted order.

4.2.5 USACO Silver: Convention

Problem (USACO 2018 February Silver): N cows arrive at times t[1..N] at a bus stop. There are M buses, each holding C cows. A bus departs when full or at a scheduled time. Assign cows to buses to minimize the maximum waiting time for any cow.

Approach: Binary search on the answer + greedy check.

This is a "binary search on the answer with greedy verification" problem:

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

int n, m, c;
vector<long long> cows;   // sorted arrival times

// Can we schedule all cows with max wait <= maxWait?
bool canDo(long long maxWait) {
    int busesUsed = 0;
    int i = 0;  // current cow index

    while (i < n) {
        busesUsed++;
        if (busesUsed > m) return false;  // ran out of buses

        // This bus serves cows starting from cow i
        // The bus must depart by cows[i] + maxWait
        long long depart = cows[i] + maxWait;

        // Fill bus with as many cows as possible (capacity c, all with arrival <= depart)
        int count = 0;
        while (i < n && count < c && cows[i] <= depart) {
            i++;
            count++;
        }
    }

    return true;
}

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

    cin >> n >> m >> c;
    cows.resize(n);
    for (long long &x : cows) cin >> x;
    sort(cows.begin(), cows.end());

    // Binary search on the maximum wait time
    long long lo = 0, hi = 1e14;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canDo(mid)) hi = mid;
        else lo = mid + 1;
    }

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

4.2.6 USACO Bronze: Herding (Greedy Observation)

Problem: Three cows stand at distinct integer positions a, b, c on a number line. In one move, you may pick any cow and teleport it to any empty integer position. Find the minimum number of moves needed to get all three cows into three consecutive integer positions (e.g., positions {k, k+1, k+2} for some integer k).

Input format:

a b c

(three space-separated integers on one line)

Sample Input:

4 7 9

Sample Output:

1

(Move cow at 9 to position 5 or 6, giving {4,5,7} or {4,7,6}... or move 4 to 8: {7,8,9}. Yes, one move suffices.)

Sample Input 2:

1 10 100

Sample Output 2:

2

(Two moves are always enough: move the two outer cows adjacent to the middle one.)

Sample Input 3:

1 2 3

Sample Output 3:

0

(Already consecutive.)

Constraints: 1 ≤ a, b, c ≤ 10^9, all three distinct.

Greedy insight: After sorting so that a ≤ b ≤ c, we know:

• 0 moves iff c - a == 2 (already consecutive).
• 2 moves always work (move a to b-1 or b+1, then move c to the other side of b).
• 1 move is possible iff one of these holds:
  • c - b == 1 (b and c are already adjacent — move a to b-1)
  • c - b == 2 (b and c have a gap of exactly 1 — move a into the gap: a → b+1... but wait, that displaces b)
  • b - a == 1 (a and b adjacent — move c to b+1)
  • b - a == 2 (a and b have a gap of 1 — move c into the gap)
  • c - a == 3 (a and c span 3 — moving b to either a+1 or c-1 makes them consecutive)

The key observation: 2 is always the upper bound. The only question is whether 0 or 1 moves suffice.

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

int main() {
    long long a, b, c;
    cin >> a >> b >> c;

    // Make sure a <= b <= c
    long long pos[3] = {a, b, c};
    sort(pos, pos + 3);
    a = pos[0]; b = pos[1]; c = pos[2];

    // 0 moves: already consecutive
    if (c - a == 2) { cout << 0; return 0; }

    // 1 move: check if moving one cow can make them consecutive
    // Options:
    // - Move a to b+1 or b-1 (if that makes 3 consecutive with c)
    // - Move c to b-1 or b+1 (if that makes 3 consecutive with a)
    // - Move b to somewhere

    // Case: after moving a, we have {b, b+1, b+2} or similar
    bool one_move = false;
    // Move a: can {b, c} be made consecutive with a new position?
    // Need b and c to differ by 1: c - b == 1 (then a → b-1 or c+1)
    if (c - b == 1) one_move = true;
    // Or c - b == 2: then a → b+1 fills the gap
    if (c - b == 2) one_move = true;

    // Move c symmetrically
    if (b - a == 1) one_move = true;
    if (b - a == 2) one_move = true;

    // Move b:
    // After moving b, we have {a, c} and new position x
    // Need {a, x, c} consecutive: x = a+1, c = a+2
    if (c - a == 2) one_move = true;  // already handled above
    // Or put b adjacent to a or c
    if (a + 1 == c - 1 && a + 1 != b) one_move = true; // if a+1 == c-1 means c-a=2 already...

    // Simpler approach: just try all possible "target" consecutive triples
    // The cows need to end up at some {x, x+1, x+2}
    // In 1 move: one cow is already at its target, two others might need to move... wait, exactly 1 cow moves
    // So two cows stay put and one moves. Check all combos.
    // Pairs that stay: (a,b), (a,c), (b,c)

    // Pair (b, c) stays: a moves. Consecutive triple containing b and c:
    // {b-2, b-1, b} with c = b (c!=b), {b-1, b, b+1} with c = b+1, {b, b+1, b+2} with c = b+2
    if (c - b == 1 || c - b == 2) one_move = true;
    // Pair (a, b) stays: c moves.
    if (b - a == 1 || b - a == 2) one_move = true;
    // Pair (a, c) stays: b moves. We need {a, x, c} consecutive.
    // c - a == 2 → already checked. c - a == 3: put b at a+1 or c-1.
    if (c - a == 3) one_move = true;

    if (one_move) { cout << 1; return 0; }

    cout << 2;
    return 0;
}

4.2.7 Common Greedy Patterns in USACO

Chapter Summary

📌 Key Takeaways

Greedy algorithms in USACO often involve:

1. Sorting the input in a clever order
2. Scanning once (or twice) with a simple update rule
3. Occasionally combining with binary search on the answer

❓ FAQ

Q1: What is the template for "binary search on answer + greedy check"?

A: Outer layer: binary search on answer X (lo=min possible, hi=max possible). Inner layer: write a check(X) function that uses a greedy strategy to verify whether X is feasible. Adjust lo/hi based on the result. The key requirement is that check must be monotone (if X is feasible, so is X+1, or vice versa).

Q2: How are USACO greedy problems different from LeetCode greedy problems?

A: USACO greedy problems typically require proving correctness (exchange argument) and are often combined with binary search and sorting. LeetCode tends to focus on simpler "always pick max/min" greedy. USACO Silver greedy problems are noticeably harder than LeetCode Medium.

Q3: When should I use priority_queue to assist greedy?

A: When you repeatedly need to extract the "current best" element (e.g., Huffman coding, minimum meeting rooms, repeatedly picking max/min values). priority_queue reduces "find the best" from O(N) to O(log N).

🔗 Connections to Other Chapters

• Chapter 4.1 covered the theory of greedy and exchange arguments; this chapter applies them to real USACO problems
• Chapter 3.3 (Binary Search) introduced the "binary search on answer" pattern used directly in the Convention problem here
• Chapter 7.1 (Understanding USACO) and Chapter 7.2 (Problem-Solving Strategies) will further discuss how to recognize greedy vs DP in contests
• Chapter 3.1 (STL) introduced priority_queue, which appears frequently in greedy simulations in this chapter

Practice Problems

Problem 4.2.1 — USACO 2016 December Bronze: Counting Haybales

Problem: N haybales placed at integer positions on a number line (positions may repeat). Q queries: how many haybales lie in the range [L, R]?

Constraints: N, Q ≤ 10^5; positions ≤ 10^9.

Example:

N=7, Q=4
Positions: 6 3 2 7 5 1 4
Queries: 2 5 / 1 1 / 4 8 / 10 15

Output:

4
1
4
0

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

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

    int n, q;
    cin >> n >> q;

    vector<int> pos(n);
    for (int &x : pos) cin >> x;
    sort(pos.begin(), pos.end());  // key: sort first to enable binary search

    while (q--) {
        int l, r;
        cin >> l >> r;

        // First position >= l
        auto lo = lower_bound(pos.begin(), pos.end(), l);
        // First position > r (one past the last position <= r)
        auto hi = upper_bound(pos.begin(), pos.end(), r);

        cout << (hi - lo) << "\n";
    }

    return 0;
}
// Time complexity: O(N log N + Q log N)

Problem 4.2.2 — USACO 2019 February Bronze: Sleepy Cow Sorting

Problem: N cows numbered 1~N stand in a line in some random order. Each operation: remove the cow at the end of the line and insert it anywhere. What is the minimum number of operations to get the line into order 1, 2, ..., N?

Example:

N=5
Order: 1 4 2 5 3

Output: 4

Line: 1 4 2 5 3
      (indices: 0 1 2 3 4)

Scan from end:
  cows[4]=3. Keep. len=1. Expect previous=2.
  cows[3]=5 ≠ 2 → stop.

Keep length = 1. Answer = 5 - 1 = 4 ✓

Verification: only "3" stays at the end; move 1,4,2,5 out and back in.
  Remove 5 → insert at front: [5,1,4,2,3]
  Remove 2 → insert in correct position ... exactly 4 operations total.

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

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

    int n;
    cin >> n;

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

    // Find longest already-sorted suffix: cows[i], cows[i+1], ..., cows[n-1]
    // Condition: cows[i] + 1 == cows[i+1] (consecutive ascending)
    int keep = 1;  // at least the last cow stays
    for (int i = n - 2; i >= 0; i--) {
        if (cows[i] + 1 == cows[i + 1]) {
            keep++;
        } else {
            break;  // suffix must be contiguous — stop at first gap
        }
    }

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

Problem 4.2.3 — Task Scheduler 🟡 Medium

Problem: N tasks labeled A–Z, each taking 1 time unit. After executing a task labeled X, the CPU must wait at least k time units before executing X again (it may run other tasks or stay idle in between). Find the minimum total time to complete all tasks.

Example:

tasks = [A, A, A, B, B, B], k = 2

Output: 8 (A→B→idle→A→B→idle→A→B)

Frame structure (k=2, f=3):
[A _ _] [A _ _] [A]
 frame1   frame2  last

Minimum time = (f-1)*(k+1) + 1 = (3-1)*(2+1)+1 = 7

(k=2, tasks=[A,A,A,B,B,B,C,C,C]):
[A B C] [A B C] [A B C] → 9 units (equals total task count)

#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> freq(26, 0);
    for (int i = 0; i < n; i++) {
        char c; cin >> c;
        freq[c - 'A']++;
    }

    int maxCount = *max_element(freq.begin(), freq.end());

    // How many task types have frequency = maxCount (they all appear in the final slot)
    int countMax = count(freq.begin(), freq.end(), maxCount);

    int ans = max(n, (maxCount - 1) * (k + 1) + countMax);

    cout << ans << "\n";
    return 0;
}
// Time complexity: O(N + 26) = O(N)

freq: A=3, B=3
maxCount = 3, countMax = 2 (both A and B appear 3 times)

ans = max(6, (3-1)*(2+1) + 2)
    = max(6, 2*3 + 2)
    = max(6, 8)
    = 8 ✓

Schedule: A→B→idle→A→B→idle→A→B

Problem 4.2.4 — USACO 2018 February Silver: Convention II 🔴 Hard

Problem: N cows ordered by seniority (lower index = higher seniority). Cow i arrives at the watering hole at time a[i] and drinks for t[i] time units (the watering device serves one cow at a time). When the device is free, the waiting cow with the highest seniority (smallest index) drinks next. Find the maximum waiting time across all cows.

Example:

N=5
Arrival times:  0 3 5 2 9
Drinking times: 4 2 3 2 1
(Cow 1 has highest seniority, cow 5 has lowest)

Output: 1

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

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

    int n;
    cin >> n;

    // {arrival time, original index (seniority), drink duration}
    vector<tuple<int,int,int>> cows(n);
    for (int i = 0; i < n; i++) {
        int a, t;
        cin >> a >> t;
        cows[i] = {a, i, t};  // original index i = seniority (0 = highest)
    }

    // Sort by arrival time
    sort(cows.begin(), cows.end());

    // Min-heap: {seniority index, arrival time, drink duration} — lowest index = highest priority
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> waiting;

    int curTime = 0;  // when the device is next free
    int maxWait = 0;
    int idx = 0;      // next cow not yet added to the heap

    while (idx < n || !waiting.empty()) {
        // Add all cows that have arrived by curTime
        while (idx < n && get<0>(cows[idx]) <= curTime) {
            auto [a, seniority, t] = cows[idx];
            waiting.push({seniority, a, t});
            idx++;
        }

        if (waiting.empty()) {
            // No one waiting — jump to the next cow's arrival
            curTime = get<0>(cows[idx]);
            continue;
        }

        // Serve the highest-seniority (lowest-index) waiting cow
        auto [seniority, arrTime, drinkTime] = waiting.top();
        waiting.pop();

        int waitTime = curTime - arrTime;  // how long this cow waited
        maxWait = max(maxWait, waitTime);

        curTime += drinkTime;  // device is free again after this cow finishes
    }

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

Cows (sorted by arrival): (0, cow1, 4), (2, cow4, 2), (3, cow2, 2)

curTime=0:
  Add cow1 (arrived 0).  waiting={cow1}
  Serve cow1: wait=0-0=0.  curTime=0+4=4.

curTime=4:
  Add cow4 (arrived 2), cow2 (arrived 3).  waiting={cow2, cow4} (cow2 has lower index)
  Serve cow2: wait=4-3=1.  curTime=4+2=6.  maxWait=1.

curTime=6:
  Serve cow4: wait=6-2=4.  curTime=6+2=8.  maxWait=4.

Answer: 4

Problem 4.2.5 — Weighted Job Scheduling 🔴 Hard (Greedy Fails → Use DP)

Problem: N jobs, each with start time s[i], end time e[i], and profit p[i]. Select a set of non-overlapping jobs to maximize total profit.

Example:

N=4
Jobs: (s=1,e=3,p=50), (s=2,e=5,p=10), (s=4,e=6,p=40), (s=6,e=7,p=70)

Output: 160 (jobs 1 + 3 + 4)

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

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

    int n;
    cin >> n;

    vector<tuple<int,int,int>> jobs(n);  // {end, start, profit}
    for (int i = 0; i < n; i++) {
        int s, e, p;
        cin >> s >> e >> p;
        jobs[i] = {e, s, p};
    }

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

    // Extract end times for binary search
    vector<int> ends;
    for (auto [e, s, p] : jobs) ends.push_back(e);

    vector<long long> dp(n + 1, 0);  // dp[i]: max profit from first i jobs (1-indexed)

    for (int i = 1; i <= n; i++) {
        auto [e, s, p] = jobs[i - 1];

        // Binary search: last job with end time <= s[i] (non-overlapping, adjacency allowed)
        int lo = 0, hi = i - 1;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (ends[mid - 1] <= s) lo = mid;
            else hi = mid - 1;
        }
        // lo = index of the last non-overlapping job (0 means none)

        dp[i] = max(dp[i - 1], dp[lo] + p);  // skip vs. take
    }

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

Sorted by end time:
idx:  1              2              3              4
      (e=3,s=1,p=50) (e=5,s=2,p=10) (e=6,s=4,p=40) (e=7,s=6,p=70)
ends: [3, 5, 6, 7]

dp[0] = 0

i=1 (e=3,s=1,p=50): find ends[j] <= 1 → none → prev=0
  dp[1] = max(dp[0], dp[0]+50) = 50

i=2 (e=5,s=2,p=10): find ends[j] <= 2 → none → prev=0
  dp[2] = max(dp[1]=50, dp[0]+10=10) = 50

i=3 (e=6,s=4,p=40): find ends[j] <= 4 → ends[0]=3 <= 4 → prev=1
  dp[3] = max(dp[2]=50, dp[1]+40=90) = 90

i=4 (e=7,s=6,p=70): find ends[j] <= 6 → ends[2]=6 <= 6 → prev=3
  dp[4] = max(dp[3]=90, dp[3]+70=160) = 160 ✓