Skip to content
Hello Python
Algorithm1 Practice2 Interview

Greedy

Make locally optimal choices only when an exchange or invariant proves global correctness. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Greedy when the prompt's constraints and required operations match this shape: Make locally optimal choices only when an exchange or invariant proves global correctness.

Pybit demonstrates Greedy in a professional Python interview workspace.
On this page · Make One Irreversible Local Choice

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Greedy Code Labs

Make One Irreversible Local Choice

A greedy algorithm commits to one locally best option and never revisits it. The implementation is easy; proving that commitment preserves a global optimum is the real work.

State the Exchange Argument

Show that any optimal solution can replace its first differing choice with the greedy choice without becoming worse. Repeating that exchange transforms an optimum into the greedy solution.

Trace Earliest-Finish Choices

Reference
def interval_choice_trace(intervals):
    trace=[]; last_end=None
    for interval in sorted(intervals,key=lambda item:(item[1],item[0])):
        accepted=last_end is None or interval[0]>=last_end
        trace.append([interval.copy(),accepted])
        if accepted:last_end=interval[1]
    return trace
Practice

Implement interval_choice_trace(intervals). Sort by end and return [interval,accepted] decisions for non-overlapping selection.

Public tests

  • Commit to earliest finish

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Sort by the Decision Key

Sorting exposes the choice order required by the proof. For interval scheduling, earliest finish leaves at least as much room for every future interval as any later finish.

Select Maximum Compatible Intervals

Reference
def max_compatible_intervals(intervals):
    count=0;last_end=None
    for start,end in sorted(intervals,key=lambda item:(item[1],item[0])):
        if last_end is None or start>=last_end:count+=1;last_end=end
    return count
Practice

Implement max_compatible_intervals(intervals). Return the maximum count of non-overlapping half-open intervals.

Public tests

  • Leave maximum room for future choices

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Know When Greedy Fails

A plausible local score is insufficient. If choices change future value in ways the exchange cannot preserve, use dynamic programming, search, or backtracking. Test a small counterexample before committing.

Explain It in an Interview

Say: “I choose the earliest finish. Given any optimal schedule, exchanging its first interval for mine cannot reduce remaining room, so an optimum with my choice exists.” Count sorting plus the linear scan and state endpoint semantics.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Greedy complete workflowO(n log n)O(n log n)Sort by finish time and accept each interval whose start is at least the previous accepted end.

Space

O(n) for the focused Select the Most Non-Overlapping Intervals implementation.

Assumptions

  • An optimal schedule can replace its first interval with the earliest-finishing interval without losing compatibility. Repeating this exchange argument on the remaining suffix proves the greedy count optimal.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Greedy invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The chosen prefix can still be extended to an optimal complete solution.
  3. Each choice permanently settles one part of the remaining problem.
  4. Prove the earliest-finish greedy choice. Preserve this claim after every transition.
  5. Track only the end of the last accepted interval. Preserve this claim after every transition.

When To Use Or Avoid Greedy

Use It When

  • Use Greedy when this precondition is stated or can be proved: An exchange argument, cut property, or maintained invariant proves the locally best legal choice is safe.
  • Use it when this maintained state removes repeated work: The chosen prefix can still be extended to an optimal complete solution.

Choose Another Tool When

  • Avoid Greedy when this precondition is absent: An exchange argument, cut property, or maintained invariant proves the locally best legal choice is safe.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: An exchange argument, cut property, or maintained invariant proves the locally best legal choice is safe.

Avoid

def maximum_non_overlapping(intervals):
    pass

Use instead

def maximum_non_overlapping(intervals):
    count = 0
    last_end = None
    for start, end in sorted(intervals, key=lambda interval: (interval[1], interval[0])):
        if last_end is None or start >= last_end:
            count += 1
            last_end = end
    return count

Where you will hit this: Select the Most Non-Overlapping Intervals(opens in a new tab)

Breaking the state transition

Sorts by start and accepts a long interval that blocks shorter compatible choices.

Prevent it: Preserve this proof obligation: Any optimal solution can be exchanged to include the chosen item without becoming worse.

Avoid

def maximum_non_overlapping(intervals):
    count=0; end=None
    for start,stop in sorted(intervals):
        if end is None or start>=end: count+=1; end=stop
    return count

Use instead

def maximum_non_overlapping(intervals):
    count = 0
    last_end = None
    for start, end in sorted(intervals, key=lambda interval: (interval[1], interval[0])):
        if last_end is None or start >= last_end:
            count += 1
            last_end = end
    return count

Where you will hit this: Select the Most Non-Overlapping Intervals(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n log n).

Avoid

def maximum_non_overlapping(intervals):
    count=0; end=None
    for start,stop in sorted(intervals):
        if end is None or start>=end: count+=1; end=stop
    return count

Use instead

def maximum_non_overlapping(intervals):
    count = 0
    last_end = None
    for start, end in sorted(intervals, key=lambda interval: (interval[1], interval[0])):
        if last_end is None or start >= last_end:
            count += 1
            last_end = end
    return count

Where you will hit this: Maximum Container Area(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.