Pattern Studioalgorithmic thinking
All patterns

Greedy Choice

Greedy Algorithms & Mathematical Optimization
Intermediate
Interactive

Choose the earliest finishing compatible interval.

Time
O(n log n)
Space
O(n)
ActiveComparingMatch / bestIn windowFrontierVisitedExcludedAnswer
No frames to display.

The idea

Greedy algorithms commit to the locally best choice only when an exchange argument proves that choice cannot hurt the global optimum. Interval scheduling sorts by finish time and repeatedly takes the next compatible interval.

Analogy

This visualization makes the state transitions behind greedy choice explicit, one decision at a time.

When to reach for it

  • The problem exhibits this pattern's defining invariant.
  • A direct brute-force approach repeats work or explores unnecessary choices.
  • You need a standard interview-ready template.

Language-independent template

sort intervals by end
last_end = -infinity
for interval in intervals:
    if interval.start >= last_end:
        choose interval
        last_end = interval.end

Complexity — time O(n log n), space O(n).

Common mistakes

  • Choosing the wrong state or invariant.
  • Updating state before preserving the value needed next.
  • Missing a boundary or base case.

Practice progression

Canonical interview problems, ordered from foundation to advanced application.

Easy
Meeting RoomsLC 252

Determine whether one person can attend every meeting.

Medium
Non-overlapping IntervalsLC 435

Remove the fewest intervals needed to eliminate all overlap.

Hard
Maximum Profit in Job SchedulingLC 1235

Choose non-overlapping jobs with maximum total profit.

Variations

Change the input to exercise another path.
Adapt the invariant to a related optimization or counting problem.