Greedy Algorithm

“Greedy Algorithm” is underspecified, so first ask for the objective, constraints, and whether choices are reversible. A greedy solution is not “take the largest” by instinct; it needs a locally safe choice and a proof. Describe the candidate rule, then use an exchange argument: take an optimal solution that differs at the first choice and show replacing that choice with the greedy one does not hurt feasibility or objective value. After the rule is justified, sort or prioritize the input, maintain a clear invariant, and explain exactly when an item is accepted or discarded. If you cannot prove the rule, say so and consider dynamic programming, a heap, or a graph formulation instead. Test ties, empty input, infeasible items, and cases designed to defeat a tempting local rule. Typical sorting-based greedy solutions cost O(n log n), but the correct complexity depends on the confirmed problem.