🌿 Greedy Algorithms#

Greedy algorithms make the locally optimal choice at each step, hoping it leads to a globally optimal solution. They work when the problem has greedy choice property and optimal substructure.

---

Core Patterns#

Pattern	Approach	Example
Sort first	Sort by key, then greedily pick	Interval scheduling, fractional knapsack
Interval scheduling	Sort by end time, greedily pick non-overlapping	Activity selection, meeting rooms
Two-pass greedy	Forward pass + backward pass	Candy distribution, temperature ratings
Jump/reach tracking	Track max reachable index	Jump Game
Local → Global	Prove local optimum = global optimum	Gas station circuit

Templates#

// Interval scheduling — non-overlapping intervals (sort by end time)
sort(intervals.begin(), intervals.end(),
     [](auto& a, auto& b){ return a[1] < b[1]; });
int count = 0, end = INT_MIN;
for (auto& iv : intervals) {
    if (iv[0] >= end) { count++; end = iv[1]; }
}

// Jump Game — max reachable index
int maxReach = 0;
for (int i = 0; i <= maxReach && i < n; i++)
    maxReach = max(maxReach, i + nums[i]);
return maxReach >= n - 1;

// Two-pass greedy (Candy)
vector<int> candy(n, 1);
for (int i = 1; i < n; i++)         // left to right
    if (ratings[i] > ratings[i-1]) candy[i] = candy[i-1] + 1;
for (int i = n-2; i >= 0; i--)      // right to left
    if (ratings[i] > ratings[i+1]) candy[i] = max(candy[i], candy[i+1] + 1);

Complexity#

Pattern	Time	Space
Sort-based greedy	O(n log n)	O(1)
Linear scan greedy	O(n)	O(1)
Two-pass greedy	O(n)	O(n)

---