# Greedy

> Local-optimal-as-global proofs.

Canonical: https://learn.significanthobbies.com/curriculum/concepts/greedy

Local-optimal-as-global proofs.

- Difficulty: core
- Tracks: DSA & Implementation

## Mental model

A greedy algorithm always picks the choice that looks best right now. It only gives the right answer when the problem has a structure (an exchange argument) that proves local choices add up correctly. When they do not, greedy quietly returns wrong answers.



## Primary sources

- [Greedy algorithm (Wikipedia)](https://en.wikipedia.org/wiki/Greedy_algorithm) (doc)

## Practice

### Activity selection greedy

Activities by end time: [1,4],[3,5],[0,6],[5,7],[8,9],[5,9]. Max non-overlapping count?

**Expected evidence:** 3 activities: [1,4], [5,7], [8,9].

## Review prompts

- What is an exchange argument, and why does a greedy algorithm need one?


## Prerequisites

- [Arrays & Hashing](https://learn.significanthobbies.com/curriculum/concepts/array-hashing)

## Related concepts

- [Intervals](https://learn.significanthobbies.com/curriculum/concepts/intervals)

## Learning paths

- [DSA Practice](https://learn.significanthobbies.com/curriculum/roadmaps/dsa-practice)