⏱ 2 min read

🌿 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)

📋 Practice Problems → ← DSA Hub 📍 Roadmap Ch 7