Greedy Algorithms

Chapter 21 · Part 4: ALGORITHMS · Est. 21 min read

Chapter Goal: Master greedy algorithms — the art of making locally optimal choices that lead to globally optimal solutions. Greedy problems require both recognizing when the greedy approach is valid AND proving it correct via the exchange argument. This chapter covers the canonical greedy patterns: interval scheduling, jump game, gas station, candy distribution, and more.

21.1 Greedy Philosophy & Proof of Correctness

What Is a Greedy Algorithm?

A greedy algorithm builds a solution by making the locally optimal choice at each step — the choice that looks best right now — without reconsidering past decisions.

Greedy: Make the best local choice → hope it leads to the global optimum
DP:     Consider ALL choices at each step → guaranteed global optimum

Two Properties Required for Greedy Correctness

1. GREEDY CHOICE PROPERTY:
   A globally optimal solution can be constructed by making greedy choices.
   Formally: there always exists an optimal solution that contains the greedy choice.

2. OPTIMAL SUBSTRUCTURE:
   After making the greedy choice, the remaining problem has the same structure
   and can be solved greedily in the same way.
   (Same requirement as DP, but greedy only needs it to hold for the greedy choice)

When Greedy Works vs. When It Fails

Greedy WORKS for:
  ✅ Activity selection (sort by end time)
  ✅ Fractional knapsack (sort by value/weight)
  ✅ Huffman coding (always merge least frequent)
  ✅ Dijkstra's shortest path (always relax nearest)
  ✅ Prim's / Kruskal's MST

Greedy FAILS for:
  ❌ 0/1 Knapsack (can't take fractions → need DP)
  ❌ Coin change with arbitrary denominations (e.g., coins={1,3,4}, amount=6)
      Greedy gives 4+1+1=3 coins, but optimal is 3+3=2 coins
  ❌ Longest path in a graph (greedy on local max ≠ global max)

The Exchange Argument — Proving Greedy Correctness

The standard proof technique: assume any optimal solution OPT, show you can transform it to match the greedy solution without worsening it.

Template:
1. Let G = greedy solution, OPT = some optimal solution
2. If G = OPT → done
3. Find the first position where G and OPT differ
4. "Exchange" OPT's choice at that position with G's greedy choice
5. Show the exchanged solution is ≥ OPT in quality
6. Repeat until OPT looks like G → G is optimal

Example: Why sort by END TIME for interval scheduling

Claim: If OPT selects interval A (end=8) first and G selects interval B (end=5),
       then we can swap A for B in OPT without reducing the count.

Proof: Interval B ends at 5 ≤ 8 (B ends earlier than A).
       Any interval compatible with A (starts ≥ 8) is also compatible with B
       (starts ≥ 8 ≥ 5).
       So swapping A for B in OPT leaves all subsequent intervals still valid.
       The count doesn't decrease.
       → Greedy choice (earliest ending) is safe. ✓

Greedy vs. DP — How to Decide

Does the problem have overlapping subproblems?
  YES → likely DP or memoization

Can the optimal solution ALWAYS be found by one greedy choice per step
(provable via exchange argument)?
  YES → greedy

If unsure: try greedy, verify with examples, then prove or disprove.
A counterexample disproves greedy immediately.

21.2 Activity Selection & Interval Scheduling

Classic Activity Selection (Maximum Non-Overlapping Intervals)

Goal: Select the maximum number of non-overlapping activities.
Greedy choice: Always pick the activity that ends earliest.
Why: Finishing early leaves maximum room for future activities.

// Sort by end time → greedily select
int activitySelection(vector<pair<int,int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](auto& a, auto& b) { return a.second < b.second; });
 
    int count = 1;
    int lastEnd = intervals[0].second;
 
    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i].first >= lastEnd) {  // No overlap
            count++;
            lastEnd = intervals[i].second;
        }
    }
    return count;
}
// Time: O(n log n), Space: O(1)

Non-overlapping Intervals (LC 435) — Minimum Removals

// Remove minimum intervals to make rest non-overlapping
// = Total intervals − maximum non-overlapping intervals
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](auto& a, auto& b) { return a[1] < b[1]; });
 
    int kept = 1, lastEnd = intervals[0][1];
    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] >= lastEnd) {
            kept++;
            lastEnd = intervals[i][1];
        }
    }
    return intervals.size() - kept;
}
// Time: O(n log n), Space: O(1)

Minimum Arrows to Burst Balloons (LC 452)

Each balloon is an interval [start, end]. An arrow at position x bursts all balloons covering x. Find minimum arrows.

int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(),
         [](auto& a, auto& b) { return a[1] < b[1]; });
 
    int arrows = 1;
    int arrowPos = points[0][1];  // Shoot at the end of first balloon
 
    for (int i = 1; i < (int)points.size(); i++) {
        if (points[i][0] > arrowPos) {  // Current balloon not burst
            arrows++;
            arrowPos = points[i][1];    // New arrow at end of current balloon
        }
        // Else: current arrow also bursts this balloon (overlapping)
    }
    return arrows;
}
// Time: O(n log n), Space: O(1)

Meeting Rooms II — Minimum Conference Rooms (LC 253)

int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> endTimes;  // Min-heap of end times
 
    for (auto& iv : intervals) {
        if (!endTimes.empty() && endTimes.top() <= iv[0])
            endTimes.pop();   // Reuse this room
        endTimes.push(iv[1]);
    }
    return endTimes.size();
}
// Time: O(n log n), Space: O(n)

Interval Scheduling — Sorting Criteria Summary

Goal	Sort By	Greedy Action
Max non-overlapping	End time ↑	Pick if start ≥ lastEnd
Min removals	End time ↑	Same as above
Min arrows	End time ↑	New arrow when start > arrowPos
Min meeting rooms	Start time ↑	Heap of end times
Merge intervals	Start time ↑	Extend if overlap

21.3 Jump Game & Reachability Patterns

Jump Game (LC 55) — Can We Reach the End?

State: maxReach = furthest index reachable so far
Greedy: at each index i ≤ maxReach, update maxReach = max(maxReach, i + nums[i])

bool canJump(vector<int>& nums) {
    int maxReach = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > maxReach) return false;      // Can't reach index i
        maxReach = max(maxReach, i + nums[i]);
        if (maxReach >= (int)nums.size()-1) return true;
    }
    return true;
}
// Time: O(n), Space: O(1)

Jump Game II (LC 45) — Minimum Jumps

Key insight: Think in "levels" like BFS. The current window [currL, currR] is what's reachable in jumps steps. From this window, find the furthest reachable index (nextR). When we exhaust the current window, increment jumps.

int jump(vector<int>& nums) {
    int jumps = 0, currEnd = 0, farthest = 0;
 
    for (int i = 0; i < (int)nums.size()-1; i++) {
        farthest = max(farthest, i + nums[i]);  // Extend as far as possible
 
        if (i == currEnd) {          // Must jump from current window
            jumps++;
            currEnd = farthest;      // New window = farthest reachable
        }
    }
    return jumps;
}
// Time: O(n), Space: O(1)
 
/*
  nums = [2,3,1,1,4]
  i=0: farthest=max(0,0+2)=2. i==currEnd(0) → jump! jumps=1, currEnd=2
  i=1: farthest=max(2,1+3)=4. i<currEnd
  i=2: farthest=max(4,2+1)=4. i==currEnd(2) → jump! jumps=2, currEnd=4
  i=3: farthest=max(4,3+1)=4. i<currEnd
  End: jumps=2 ✓ (reach index 4 = last)
*/

Jump Game VII (Condition-Based Jumps)

// Can reach index n-1 from index 0?
// From index i, can jump to [i+minJump, i+maxJump] if nums[j]=='0'
bool canReach(string s, int minJump, int maxJump) {
    int n = s.size();
    vector<bool> dp(n, false);
    dp[0] = true;
    int prevTrue = 0;  // Count of reachable positions up to current window
 
    for (int i = 1; i < n; i++) {
        if (s[i] == '1') continue;
        if (i - maxJump > 0) prevTrue -= dp[i - maxJump - 1];  // Remove out-of-window
        prevTrue += dp[max(0, i - minJump)];                    // Add new in-window
        if (prevTrue > 0) dp[i] = true;
    }
    return dp[n-1];
}

21.4 Fractional Knapsack

Unlike 0/1 Knapsack (DP), fractional knapsack allows taking fractions of items. The greedy approach — sort by value-to-weight ratio, take greedily — is optimal.

struct Item { double weight, value; };
 
double fractionalKnapsack(double W, vector<Item>& items) {
    // Sort by value/weight ratio (descending)
    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.value/a.weight > b.value/b.weight;
    });
 
    double totalValue = 0.0;
    for (auto& item : items) {
        if (W <= 0) break;
        double take = min(item.weight, W);
        totalValue += take * (item.value / item.weight);
        W -= take;
    }
    return totalValue;
}
// Time: O(n log n), Space: O(1)
 
/*
  Why greedy is correct: Exchange argument.
  If optimal OPT takes less of item A (high ratio) and more of B (low ratio),
  swapping: reduce B by ε, increase A by ε (same weight, higher value).
  → OPT improves or stays the same after swap → greedy choice is at least as good.
*/

Maximum Units on a Truck (LC 1710) — Greedy Variant

int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
    sort(boxTypes.begin(), boxTypes.end(),
         [](auto& a, auto& b) { return a[1] > b[1]; });  // Most units first
 
    int units = 0;
    for (auto& box : boxTypes) {
        int take = min(box[0], truckSize);
        units += take * box[1];
        truckSize -= take;
        if (truckSize == 0) break;
    }
    return units;
}
// Time: O(n log n), Space: O(1)

21.5 Huffman Coding — Greedy Encoding (Concept)

The Problem

Assign variable-length binary codes to characters so that more frequent characters get shorter codes. Total encoding length = Σ (frequency × code length).

The Greedy Insight

Always combine the two nodes with the smallest frequencies first. This minimizes the total weighted path length.

Characters: {a:5, b:9, c:12, d:13, e:16, f:45}

Step 1: Combine a(5) and b(9) → ab(14)
Step 2: Combine ab(14) and c(12) → abc(26)
Step 3: Combine d(13) and e(16) → de(29)
Step 4: Combine abc(26) and de(29) → abcde(55)
Step 5: Combine abcde(55) and f(45) → root(100)

Codes: f=0, c=100, d=1010, e=1011, a=1100, b=1101
Total bits = 45×1 + 12×3 + 13×4 + 16×4 + 5×6 + 9×6 = 224

// Concept implementation using priority queue
int huffmanCost(vector<int>& freqs) {
    priority_queue<int, vector<int>, greater<int>> minPQ(freqs.begin(), freqs.end());
    int totalCost = 0;
 
    while (minPQ.size() > 1) {
        int first  = minPQ.top(); minPQ.pop();
        int second = minPQ.top(); minPQ.pop();
        int merged = first + second;
        totalCost += merged;
        minPQ.push(merged);
    }
    return totalCost;  // Total weighted path length
}
// Time: O(n log n), Space: O(n)
// This is exactly LC 1167 "Minimum Cost of Connecting Sticks"

21.6 Gas Station & Circular Greedy

Gas Station (LC 134)

Find the starting gas station to complete a circular route. Return -1 if impossible.

Key observations:

If total gas ≥ total cost → a solution always exists (and is unique)
If we start at station i and run out at station j, then no station between i and j can be the starting point (they would inherit the same deficit)
Therefore: start from 0, when tank goes negative → set start = next station

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int totalGas = 0, totalCost = 0;
    int tank = 0, start = 0;
 
    for (int i = 0; i < (int)gas.size(); i++) {
        totalGas  += gas[i];
        totalCost += cost[i];
        tank += gas[i] - cost[i];
 
        if (tank < 0) {
            start = i + 1;   // Can't reach i+1 from any previous start
            tank = 0;        // Reset tank for new candidate
        }
    }
    return (totalGas >= totalCost) ? start : -1;
}
// Time: O(n), Space: O(1)
 
/*
  Why this works:
  If tank goes negative at station i (coming from start), no station
  in [start, i] can be the starting point because:
  - From 'start': net gain from start to i is negative (tank < 0)
  - From any k in (start, i]: the partial sum gas[k]-cost[k] + ... + gas[i]-cost[i]
    must also be negative (otherwise starting from k would have prevented start's failure)
  So the only candidate is i+1.
*/

21.7 Two-Pass Greedy — Candy & Rating Problems

Candy (LC 135)

Distribute minimum candy so that:

Every child gets ≥ 1 candy
Children with higher rating than their neighbor get more candy

Two-pass greedy:

Pass 1 (left→right): if ratings[i] > ratings[i-1], give more than left neighbor
Pass 2 (right→left): if ratings[i] > ratings[i+1], give more than right neighbor (take max)

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> candies(n, 1);
 
    // Pass 1: Left to right — handle left constraint
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1])
            candies[i] = candies[i-1] + 1;
    }
 
    // Pass 2: Right to left — handle right constraint
    for (int i = n-2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1])
            candies[i] = max(candies[i], candies[i+1] + 1);
    }
 
    return accumulate(candies.begin(), candies.end(), 0);
}
// Time: O(n), Space: O(n)
 
/*
  ratings = [1, 0, 2]
  After pass 1: [1, 1, 2]  (2 > 0 → candies[2] = candies[1]+1)
  After pass 2: [2, 1, 2]  (ratings[0]=1 > ratings[1]=0 → candies[0]=max(1,1+1)=2)
  Total = 5
 
  ratings = [1, 2, 2]
  After pass 1: [1, 2, 1]  (2==2 at i=2, so no increase)
  After pass 2: [1, 2, 1]  (2==2, no change)
  Total = 4
*/

21.8 Partition & Labeling Greedy

Partition Labels (LC 763)

Partition string s into as many parts as possible such that each letter appears in at most one part.

Greedy: For each character, record its last occurrence. Process left to right, extending the current partition until we've seen all characters whose last occurrence is within the current partition.

vector<int> partitionLabels(string s) {
    // Record last occurrence of each character
    int last[26] = {};
    for (int i = 0; i < (int)s.size(); i++) last[s[i]-'a'] = i;
 
    vector<int> result;
    int start = 0, end = 0;
 
    for (int i = 0; i < (int)s.size(); i++) {
        end = max(end, last[s[i]-'a']);  // Extend partition to include all occurrences
 
        if (i == end) {                  // Reached the end of current partition
            result.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return result;
}
// Time: O(n), Space: O(1) — 26-element array
 
/*
  s = "ababcbacadefegdehijhklij"
  last: a=8, b=5, c=7, d=14, e=15, f=11, g=13, h=19, i=22, j=23, k=20, l=21
 
  i=0 ('a'): end=max(0,8)=8
  i=1 ('b'): end=max(8,5)=8
  ...
  i=8 ('a'): end=8 == i=8 → partition [0..8], size=9
  i=9 ('d'): end=max(9,14)=14
  ...
  i=15('e'): end=max(14,15)=15 == i=15 → partition [9..15], size=7
  ...
  i=23('j'): end=23 == i=23 → partition [16..23], size=8
  Result: [9, 7, 8]
*/

Task Scheduler (LC 621) — Greedy Math

int leastInterval(vector<char>& tasks, int n) {
    int freq[26] = {};
    for (char t : tasks) freq[t-'A']++;
 
    int maxFreq   = *max_element(freq, freq+26);
    int maxCount  = count(freq, freq+26, maxFreq);
 
    // Formula: max(tasks.size(), (maxFreq-1)*(n+1) + maxCount)
    // (maxFreq-1) "cycles" of length (n+1) + the last batch of maxCount tasks
    return max((int)tasks.size(), (maxFreq-1)*(n+1) + maxCount);
}
// Time: O(n), Space: O(1)
 
/*
  tasks = [A,A,A,B,B,B], n=2
  maxFreq=3, maxCount=2 (A and B both appear 3 times)
  (3-1)*(2+1) + 2 = 6+2 = 8
  Sequence: A B _ A B _ A B → 8 slots ✓
  tasks.size()=6, max(6,8)=8
*/

Boats to Save People (LC 881) — Two-Pointer Greedy

int numRescueBoats(vector<int>& people, int limit) {
    sort(people.begin(), people.end());
    int l = 0, r = people.size()-1, boats = 0;
 
    while (l <= r) {
        if (people[l] + people[r] <= limit) l++;  // Pair lightest with heaviest
        r--;   // Heaviest always takes a boat (alone or with lightest)
        boats++;
    }
    return boats;
}
// Time: O(n log n), Space: O(1)
// Greedy: always try to pair the heaviest person with the lightest

Assign Cookies (LC 455)

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int child = 0, cookie = 0;
    while (child < (int)g.size() && cookie < (int)s.size()) {
        if (s[cookie] >= g[child]) child++;  // Cookie satisfies this child
        cookie++;
    }
    return child;
}
// Greedy: assign the smallest sufficient cookie to each child (sorted)
// Time: O(n log n + m log m), Space: O(1)

21.9 Sample Problems

Problem 1 — Assign Cookies (Easy) — LC 455

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(),g.end()); sort(s.begin(),s.end());
    int child=0,cookie=0;
    while(child<(int)g.size()&&cookie<(int)s.size()){
        if(s[cookie]>=g[child]) child++;
        cookie++;
    }
    return child;
}
// Time: O(n log n), Space: O(1)

Problem 2 — Non-overlapping Intervals (Medium) — LC 435

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(),intervals.end(),[](auto&a,auto&b){return a[1]<b[1];});
    int kept=1, lastEnd=intervals[0][1];
    for(int i=1;i<(int)intervals.size();i++)
        if(intervals[i][0]>=lastEnd){kept++;lastEnd=intervals[i][1];}
    return intervals.size()-kept;
}
// Time: O(n log n), Space: O(1)

Problem 3 — Minimum Number of Arrows to Burst Balloons (Medium) — LC 452

int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(),points.end(),[](auto&a,auto&b){return a[1]<b[1];});
    int arrows=1, pos=points[0][1];
    for(int i=1;i<(int)points.size();i++)
        if(points[i][0]>pos){arrows++;pos=points[i][1];}
    return arrows;
}
// Time: O(n log n), Space: O(1)

Problem 4 — Jump Game (Medium) — LC 55

bool canJump(vector<int>& nums) {
    int maxReach=0;
    for(int i=0;i<(int)nums.size();i++){
        if(i>maxReach) return false;
        maxReach=max(maxReach,i+nums[i]);
    }
    return true;
}
// Time: O(n), Space: O(1)

Problem 5 — Jump Game II (Medium) — LC 45

int jump(vector<int>& nums) {
    int jumps=0, currEnd=0, farthest=0;
    for(int i=0;i<(int)nums.size()-1;i++){
        farthest=max(farthest,i+nums[i]);
        if(i==currEnd){jumps++;currEnd=farthest;}
    }
    return jumps;
}
// Time: O(n), Space: O(1)

Problem 6 — Gas Station (Medium) — LC 134

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int totalGas=0,totalCost=0,tank=0,start=0;
    for(int i=0;i<(int)gas.size();i++){
        totalGas+=gas[i]; totalCost+=cost[i];
        tank+=gas[i]-cost[i];
        if(tank<0){start=i+1;tank=0;}
    }
    return totalGas>=totalCost?start:-1;
}
// Time: O(n), Space: O(1)

Problem 7 — Candy (Hard) — LC 135

int candy(vector<int>& ratings) {
    int n=ratings.size();
    vector<int> c(n,1);
    for(int i=1;i<n;i++)
        if(ratings[i]>ratings[i-1]) c[i]=c[i-1]+1;
    for(int i=n-2;i>=0;i--)
        if(ratings[i]>ratings[i+1]) c[i]=max(c[i],c[i+1]+1);
    return accumulate(c.begin(),c.end(),0);
}
// Time: O(n), Space: O(n)

Problem 8 — Task Scheduler (Medium) — LC 621

int leastInterval(vector<char>& tasks, int n) {
    int freq[26]={};
    for(char t:tasks) freq[t-'A']++;
    int maxF=*max_element(freq,freq+26);
    int maxC=count(freq,freq+26,maxF);
    return max((int)tasks.size(),(maxF-1)*(n+1)+maxC);
}
// Time: O(n), Space: O(1)

Problem 9 — Partition Labels (Medium) — LC 763

vector<int> partitionLabels(string s) {
    int last[26]={};
    for(int i=0;i<(int)s.size();i++) last[s[i]-'a']=i;
    vector<int> res; int start=0,end=0;
    for(int i=0;i<(int)s.size();i++){
        end=max(end,last[s[i]-'a']);
        if(i==end){res.push_back(end-start+1);start=i+1;}
    }
    return res;
}
// Time: O(n), Space: O(1)

Problem 10 — Boats to Save People (Medium) — LC 881

int numRescueBoats(vector<int>& people, int limit) {
    sort(people.begin(),people.end());
    int l=0,r=people.size()-1,boats=0;
    while(l<=r){
        if(people[l]+people[r]<=limit) l++;
        r--; boats++;
    }
    return boats;
}
// Time: O(n log n), Space: O(1)

Problem 11 — Maximum Swap (Medium) — LC 670

Given an integer, swap two digits at most once to make the largest number.

Greedy: Find the rightmost occurrence of each digit. For each digit from left to right, check if there's a larger digit to its right — swap with the rightmost occurrence of the largest such digit.

int maximumSwap(int num) {
    string s = to_string(num);
    int n = s.size();
 
    // Record last position of each digit (0-9)
    int last[10] = {};
    for (int i = 0; i < n; i++) last[s[i]-'0'] = i;
 
    // Try to swap current digit with the largest later digit
    for (int i = 0; i < n; i++) {
        for (int d = 9; d > s[i]-'0'; d--) {
            if (last[d] > i) {        // A larger digit exists to the right
                swap(s[i], s[last[d]]);
                return stoi(s);
            }
        }
    }
    return num;  // No beneficial swap
}
// Time: O(n), Space: O(1)

Problem 12 — Minimum Cost to Hire K Workers (Hard) — LC 857

Hire exactly k workers. Each worker i has a quality[i] and min wage[i]. If you hire a group, each worker must be paid (wage/quality) ≥ their own ratio. All must be paid proportionally to quality. Minimize total wage.

Key insight: Sort by wage/quality ratio. For a fixed "captain" (highest ratio in the group), all others are paid captain_ratio × their_quality. Use a max-heap to keep the k smallest quality workers.

double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
    int n = quality.size();
    // Sort by wage/quality ratio
    vector<pair<double,int>> workers(n);
    for (int i = 0; i < n; i++)
        workers[i] = {(double)wage[i]/quality[i], quality[i]};
    sort(workers.begin(), workers.end());
 
    priority_queue<int> maxQualHeap;   // Max-heap of quality values
    int qualSum = 0;
    double ans = DBL_MAX;
 
    for (auto [ratio, q] : workers) {
        maxQualHeap.push(q);
        qualSum += q;
 
        if ((int)maxQualHeap.size() > k) {
            qualSum -= maxQualHeap.top();
            maxQualHeap.pop();
        }
 
        if ((int)maxQualHeap.size() == k) {
            ans = min(ans, ratio * qualSum);  // Captain = current ratio
        }
    }
    return ans;
}
// Time: O(n log n + n log k), Space: O(n)

21.10 LeetCode Problem Set

#	Problem	Difficulty	Core Technique	Link
1	Assign Cookies	Easy	Sort + two-pointer greedy	LC 455
2	Jump Game	Medium	Max-reach tracking	LC 55
3	Jump Game II	Medium	Window-based BFS-like greedy	LC 45
4	Non-overlapping Intervals	Medium	Sort by end, count kept	LC 435
5	Minimum Arrows to Burst Balloons	Medium	Sort by end, track arrow pos	LC 452
6	Gas Station	Medium	Running sum + reset start	LC 134
7	Partition Labels	Medium	Last occurrence + extend partition	LC 763
8	Candy	Hard	Two-pass left-right greedy	LC 135

Suggested order: #1 (Assign Cookies) — pure sort + greedy. #2 and #3 (Jump Game I & II) — reachability greedy, both O(n). #4 and #5 (Interval problems) — master the "sort by end time" pattern. #6 (Gas Station) — the circular reset greedy. #7 (Partition Labels) — last occurrence pattern. Save #8 (Candy) for last — two-pass greedy requires clear reasoning about why each pass handles one constraint direction.