CodeWithYash

Intermediate · Module 16 · Lesson 1

Greedy-choice property

Know when a local decision is safe.

15–25 min readLesson 89 of 123

Lesson 89 of 123

1d streak

Theory lesson · Step-by-step

Understand Greedy-choice property

Know when a local decision is safe.

Worked approach

Trace the reasoning step by step

  1. 1State the candidate ordering and local choice made by Greedy-choice property.
  2. 2Identify the feasibility condition maintained by the partial solution.
  3. 3Use an exchange or stays-ahead argument to justify the choice.
  4. 4Commit the choice and remove candidates it makes impossible.
  5. 5Search for a counterexample before trusting the greedy rule.

Concrete example

Select maximum non-overlapping intervals.

  1. 1Choose the interval finishing earliest.
  2. 2Discard intervals starting before its finish.

The earliest finish leaves at least as much room as any alternative.

What must remain true (Loop Invariant)

After every choice in Greedy-choice property, the partial solution can still be extended to an optimum under the proved exchange or stays-ahead argument.

Cost Model

Complexity & Trade-offs

Order and scan
Usually O(n log n)
O(1) to O(n)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Scheduling, reachability, coding, matching resources, and minimum-cost growth.
  • Problems with an exchange proof or matroid-like safe choices.
  • Online decisions that maintain a best frontier.

Common mistakes

  • Choosing a plausible local optimum without a proof.
  • Using the wrong sorting key.
  • Applying greedy reasoning when choices interact through future state.

Practice prompts

  • Reproduce the worked Greedy-choice property example without looking at the trace.
  • Change one input condition and explain whether the Greedy-choice property invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.