Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Greedy Algorithms

A greedy algorithm makes the locally best choice at each step and never goes back. It is fast and simple — but it is only correct when the problem has the right structure.

When does greedy work?

  1. Greedy-choice property — a globally optimal answer can be reached by making the best local choice first.
  2. Optimal substructure — after that choice, the rest is a smaller problem of the same kind.

If you can find a counter-example where the local best choice loses, greedy is wrong → think DP.

Classic counter-example: coin change with coins {1, 3, 4} and amount 6. Greedy takes 4 + 1 + 1 (3 coins), but 3 + 3 (2 coins) is better. With Indian coins {1, 2, 5, 10} greedy works; for arbitrary coins, use DP.

Pattern 1: interval scheduling (activity selection)

Maximum number of non-overlapping meetings. Sort by end time, always take the meeting that ends first.

int maxMeetings(vector<pair<int,int>>& m) {        // {start, end}
    sort(m.begin(), m.end(), [](auto& a, auto& b) { return a.second < b.second; });
    int count = 0, lastEnd = INT_MIN;
    for (auto& [s, e] : m)
        if (s >= lastEnd) { count++; lastEnd = e; }
    return count;
}

Why it works: the meeting that ends earliest leaves the most room for the rest — an exchange argument shows swapping it into any optimal answer never makes things worse.

Related: non-overlapping intervals (remove the fewest = n − max kept), minimum arrows to burst balloons.

Pattern 2: merge intervals

Sort by start; extend the current interval while the next one overlaps.

vector<vector<int>> merge(vector<vector<int>>& iv) {
    sort(iv.begin(), iv.end());
    vector<vector<int>> res;
    for (auto& x : iv) {
        if (res.empty() || res.back()[1] < x[0]) res.push_back(x);
        else res.back()[1] = max(res.back()[1], x[1]);
    }
    return res;
}

Pattern 3: jump game

Track the farthest index reachable so far.

bool canJump(vector<int>& a) {
    int reach = 0;
    for (int i = 0; i < a.size(); i++) {
        if (i > reach) return false;
        reach = max(reach, i + a[i]);
    }
    return true;
}

Jump game II (min jumps): BFS-like levels — count a jump each time you pass the end of the current range.

Pattern 4: fractional knapsack

Items can be broken, so take items by value/weight ratio, highest first. (The 0/1 knapsack, where items cannot be broken, needs DP.)

Pattern 5: two-pointer greedy

Pattern 6: minimum platforms / meeting rooms

Sort arrivals and departures separately; walk through them — +1 on arrival, −1 on departure; the maximum is the answer. (Or a min-heap of end times.)

Pattern 7: greedy with a heap

Proving a greedy solution (for interviews)

Classic problems

Problem Greedy rule
N meetings in one room / activity selection earliest end first
Merge intervals sort by start
Non-overlapping intervals earliest end first
Jump game I & II farthest reach
Gas station reset start when the tank goes negative
Minimum platforms sweep arrivals/departures
Fractional knapsack best value/weight first
Assign cookies / boats sort + two pointers
Candy two passes (left, right)

Practise in the Greedy section.

Interview one-liners

More DSA notes