What is a greedy algorithm?

A greedy algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. It makes the locally optimal choice at each stage with the hope of finding a global optimum.

When does a greedy approach work?

A greedy algorithm works if a problem exhibits two properties: the greedy choice property (a global optimum can be arrived at by selecting a local optimum) and optimal substructure (an optimal solution to the problem contains optimal solutions to subproblems). Proving these properties is key to knowing if a greedy strategy is valid.

Optimization Algorithms

Greedy Algorithms for Interviews

Learn the art of making the locally optimal choice to achieve a global optimum. This guide covers the greedy approach with classic examples like Activity Selection, with AI-powered hints.

Activity Selection Problem

The Activity Selection Problem is a classic example of a problem that can be solved using a greedy algorithm. The goal is to select the maximum number of non-overlapping activities from a given set.

                            function activitySelection(start, finish) {
                            let n = start.length;
                            // Sort activities by finish time
                            let activities = start.map((s, i) => ({ start: s, finish: finish[i] }));
                            activities.sort((a, b) => a.finish - b.finish);
                            
                            let i = 0;
                            let count = 1;
                            for (let j = 1; j < n; j++) {
                            if (activities[j].start >= activities[i].finish) {
                            count++;
                            i = j;
                            }
                            }
                            return count;
                            }
                        

AI Coach Hint: The greedy choice here is to always pick the next activity that finishes earliest. This leaves the maximum amount of time for other activities. Proving that this local choice leads to a global optimum is the key to understanding why the greedy approach works for this problem.