Greedy & Intervals

Greedy Choice

Make the locally best choice when an exchange argument shows it is safe.

Medium, about 90 minutes to practise.

1Understand

The idea

Make the choice that looks best right now and never revisit it. That is only correct when you can argue that swapping the greedy choice into any optimal solution keeps it optimal (an exchange argument). The work is usually in finding what to sort by, such as the earliest end, the largest gain or the tightest deadline.

Intuition

Make the choice that looks best right now and never revisit it. That is only correct when you can argue an exchange argument: swapping the greedy choice into any optimal solution keeps it optimal (or improves it).

The work is usually finding what to sort by, earliest end time, largest gain, tightest deadline. If you cannot sketch why a local choice is safe, fall back to DP.

Greedy solutions are often short once the ordering is right; wrong ordering is the usual bug.

What you will be able to do

  • Justify the greedy choice
  • Spot when greedy fails and DP is needed

When to use it

  • Jump game / gas station style reachability
  • Minimum number of X to cover Y
  • Choosing the earliest-ending option first

2See it

Walkthrough

Jump game reach

a = [2, 3, 1, 1, 4], track farthest reachable index.

1 / 6

i
2
3
1
1
4
01234
i → index 0

reach = 0. Start at i=0 (always reachable).

reach = 0

Live template

Line 4 active

1reach = 0
2for i, step in enumerate(a):
3 if i > reach: return False
4 reach = max(reach, i + step)
5return True

Complexity: time O(n) or O(n log n), space O(1)

Usually O(n log n) with a sort, or O(n) when a linear scan suffices. DP alternatives are often O(n²). Prefer greedy when the exchange argument is clear; otherwise DP is safer.

Read the walkthrough as text

Jump game II (min jumps). nums = [2,3,1,1,4].

  1. Greedy BFS layers on the array: within the current jump reach, track the farthest you can get.
  2. When the scan index hits the end of the current layer, bump jumps and set the new layer end to that farthest.
  3. From index 0, layer end 0, farthest becomes 2; jump → layer end 2.
  4. Inside 1..2, farthest becomes 4; next jump reaches the end → answer 2.

Choosing the earliest end for interval scheduling is the same "safe local choice" spirit.

3Recognise it

Kinds of problems (11)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Reachability (jump game)

    Example. Can you reach the last index from jumps[i]?

    How. Track farthest index reachable; fail if i > farthest.

  • Gas station

    Example. Complete a circuit with gas and cost arrays.

    How. If total gas ≥ total cost, start from index where tank never goes negative when cycled.

  • Assign cookies / matching

    Example. Maximize children satisfied with smallest cookies.

    How. Sort both; two pointers match smallest cookie that fits each child.

  • Partition labels

    Example. Partition string so each letter appears in one part.

    How. Record last index of each letter; extend current part to max last seen.

  • Minimum arrows / platforms

    Example. Minimum arrows to burst all balloons (intervals).

    How. Sort by end; shoot at end; skip overlapping intervals covered.

  • Grouping with counts (hand of straights)

    Example. Split into groups of k consecutive numbers.

    How. Count frequencies; greedily start groups from smallest available keys.

  • Sort by a derived key (two-city scheduling, deadlines)

    Example. Schedule jobs by profit/time or fly to cheaper city first.

    How. Sort by deadline or delta; prove greedy choice safe for that key.

  • Two passes, left and right (candy)

    Example. Minimum candies with neighbour rating rules.

    How. Left pass increase if rating rises; right pass enforce from the right.

  • Track a range of possibilities (valid parenthesis string)

    Example. Remove min parentheses to make string valid.

    How. Track open count range [lo, hi] allowed after each character.

  • Local fix-ups while scanning (place flowers, non-decreasing array)

    Example. Place flowers with gap rule in one pass.

    How. Greedy plant when previous two slots empty; or raise arr[i] to arr[i-1] while scanning.

  • Turn-by-turn simulation with queues

    Example. Rotating queue simulation (e.g. queue of tasks).

    How. Simulate rounds with deque or counters; greedy pick local optimum each turn.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Unsafe greedy

    Why it happens. First local rule that seems optimal often passes small tests.

    How it fails. Coin change by largest coin fails [1,3,4] amount 6, greedy is not optimal.

    Fix. Prove exchange argument or use DP when counterexample exists.

  • Wrong sort key

    Why it happens. Sorting by start is natural for intervals.

    How it fails. Minimum arrows sorted by start, miss overlap chain that sorting by end covers.

    Fix. Non-overlap minimisation sorts by end; merge often by start, read variant.

  • Local check only

    Why it happens. Each step feasible so the whole plan feels feasible.

    How it fails. Jump game checks jump[i]>0 only, misses that earlier index cannot be reached.

    Fix. Carry global invariant (farthest reach, running sum) not just local rule.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons