Skip to content

Greedy

Lesson 1 of 2 in Optimization · 35 min · Intermediate

Take the best-looking move now — when you can prove it's safe.

Introduction

You have one meeting room and a pile of meeting requests for today. Which request do you say yes to first, if you want to fit in as many as you can?

Say the day has four requests: 8–12, 9–10, 10–11 and 11–12. The one that starts first (8–12) sounds natural to grab, but it fills the whole morning and leaves room for nothing else. You attend one meeting.

Now try one rule instead: always say yes to the request that ends soonest, as long as it doesn't clash with what you've already booked. That books 9–10, then 10–11, then 11–12. Three meetings, from a rule you can say in one breath.

Lesson overview

This lesson will show you how to:

  • Explain why finishing earliest leaves the most room for later picks.
  • Trace the earliest-end rule through a list of meetings, keeping or dropping each.
  • Trace the farthest-reach rule through the jump game, one index at a time.
  • Spot when a locally best pick is unsafe and dynamic programming is needed.
  • Implement the sort-then-scan template for interval scheduling in O(n log n).

The picture

intervals1–202–311–323–43iends first, so keep itstarts before 3: overlapnext one to judgeArray intervals with 4 slots: 1–2, 2–3, 1–3, 3–4. Pointers: i at index 2. Marked: index 0 found; index 1 found; index 2 compare.

Mental model

Packing your day, you keep asking one question: of the things left, which one frees me up soonest? You say yes to that one, and you never reopen the decision.

Each yes leaves as much of the day as possible for whatever is still to come.

Take the pick that leaves the most room, never look back, and be able to argue that no other pick could have done better.

Words to know

greedy choice
The pick that looks best right now, made without looking ahead and never undone. In scheduling it is the interval that ends earliest.
local optimum
The best option at a single step, judged only by what you can see right now.
global optimum
The best answer for the whole problem. Greedy is only correct when a string of local optima adds up to this.
exchange argument
The proof that makes greedy safe: take any best answer, swap its first pick for the greedy pick, and show it is still best.
counterexample
A small input where the greedy rule gives a worse answer than the best one. A single counterexample is enough to throw the rule out.
sort key
The field you sort by so the best pick comes first. For meetings it is the end time, not the start time or the length.
overlap
Two intervals share some time. Touching at one moment (one ends at 3, the next starts at 3) does not count.
reach
In Jump Game, the farthest index any jump so far can land on. It only ever grows.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The data is intervals or tasks with start and end times, and you have to pick or schedule as many as possible.
  • Yes: The statement asks for a minimum or maximum count, like the most meetings, the fewest arrows or the fewest removals, and sorting by one field makes the best pick obvious.
  • Yes: You can say why taking the best-looking option now can never hurt later, for example because you could swap it into any other plan.
  • Yes: You scan once, keeping a single running number such as the farthest reach or the last end, and each step needs only that number.

Not this when

  • No: A choice now can block a better combination later, like coins 1, 3, 4 for amount 6. Greedy gives 3 coins where 2 is possible, so use dynamic-programming.
  • No: You must count the number of ways or list every solution. One confident pass can't do that; reach for recursion or dynamic-programming.
  • No: You can't explain why the pick is safe, and a small counterexample breaks it. Don't trust the rule until you have the argument.

Which pattern fits?

  1. Which pattern? 1 of 5

    You have a list of meetings [start, end] and one room. Find the largest number of meetings you can attend with no overlap.

  2. Which pattern? 2 of 5

    Given coins [1, 3, 4] and an amount of 6, find the fewest coins that add up to it.

  3. Which pattern? 3 of 5

    Numbers keep arriving in a stream. After each one, report the 3rd largest number seen so far.

  4. Which pattern? 4 of 5

    nums[i] is how far you can jump from index i. Starting at index 0, decide whether you can reach the last index.

  5. Which pattern? 5 of 5

    Given a string, find the length of the longest substring that has no repeating characters.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1sort intervals by end, earliest first
  2. 2removed = 0, last_end = −∞
  3. for each (start, end) in the sorted list:
  4. 3if start >= last_end:
  5. 4keep it: last_end = end
  6. else:
  7. 5drop it: removed += 1
  8. 6return removed

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda iv: iv[1])
    removed = 0
    last_end = float("-inf")
    for start, end in intervals:
        if start >= last_end:
            last_end = end
        else:
            removed += 1
    return removed
Time · O(n log n)Space · O(1) beyond the sort
  • Why sort by end? Sort by start and one long meeting like 0–10 blocks three short ones. Sort by shortest first and a short 3–5 sitting between 1–4 and 4–8 blocks both, though those two fit together. Only the earliest end always leaves the most room.
  • Touching is fine: if one interval ends at 3 and the next starts at 3, they don't overlap. That is why the test is start >= last_end, not start > last_end.
  • The exchange argument in four lines: take any best schedule, swap its first interval for the earliest-ending one, and note that it ends no later, so everything after it still fits. The schedule is no worse, so some best schedule starts with the greedy pick. Repeat for what remains.
  • Sorting costs O(n log n) and the sweep is a single O(n) pass, so the sort dominates. Beyond the sort you keep only two numbers: last_end and removed.
  • Greedy is not a default; it is a claim you have to defend. Always-take-the-biggest-coin works for coins like 1, 5, 10, 25, but with coins [1, 3, 4] and amount 6 it picks 4 + 1 + 1 = 3 coins while 3 + 3 = 2 is best. When a choice can block a better combination later, use dynamic-programming.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Each number in nums is the farthest you can jump from that index. Starting at index 0, return true if you can reach the last index, otherwise false.

Input

nums = [3,2,1,0,4]

Output

false

Approach

  1. Track reach, the farthest index any jump so far can land on. It starts at 0.
  2. Index 0 lets you jump 3, so reach = 3. Indexes 1 and 2 also land on 3 (1 + 2 and 2 + 1), and index 3 jumps 0, so reach stays 3.
  3. Index 4 is past reach: no jump can land there. You are stuck before the end, so the answer is false.
  4. If reach ever covers the last index you can stop early, because the answer is then true.
def can_jump(nums):
    last = len(nums) - 1
    reach = 0
    for i in range(last + 1):
        if i > reach:
            break
        reach = max(reach, i + nums[i])
        if reach >= last:
            break
    return reach >= last
Time · O(n)Space · O(1)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. You want the most non-overlapping meetings. Which sort order makes the greedy pick safe?
  2. Coins are [1, 3, 4] and the amount is 6. What does "always take the biggest coin that fits" give, and what is the best possible?
  3. What does an exchange argument show?
  4. You find a small input where your greedy rule gives a worse answer than the best. What should you do?
  5. For nums = [1, 0, 2] in Jump Game, what does the reach scan conclude?

Question 1 of 5

You want the most non-overlapping meetings. Which sort order makes the greedy pick safe?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 10 solved

  1. Solve Assign Cookies (opens in a new tab) (LeetCode, easy)

    Hint: Sort children by greed and cookies by size, then give each child the smallest cookie that still satisfies them.

  2. Solve Best Time to Buy and Sell Stock II (opens in a new tab) (LeetCode, medium)

    Hint: You may trade every day. Think about each rise from one day to the next on its own, rather than hunting for one big buy and sell.

  3. Solve Gas Station (opens in a new tab) (LeetCode, medium)

    Hint: If total gas is less than total cost, no start works. Otherwise, when your tank first goes negative, every station up to there is a bad start.

  4. Solve Partition Labels (opens in a new tab) (LeetCode, medium)

    Hint: Record the last position of every letter. Keep stretching the current part to cover those last positions, and cut when i catches up.

  5. Solve Task Scheduler (opens in a new tab) (LeetCode, medium)

    Hint: The most frequent task forces the gaps. Lay it out first, then check whether the other tasks can fill the gaps or leave idle slots.

  6. Solve Two City Scheduling (opens in a new tab) (LeetCode, medium)

    Hint: Look at costA − costB for each person: it says how much more they prefer one city. Sort by that gap.

  7. Solve Queue Reconstruction by Height (opens in a new tab) (LeetCode, medium)

    Hint: Place people from tallest to shortest, so a shorter person never changes the count of someone already placed.

  8. Solve Candy (opens in a new tab) (LeetCode, hard)

    Hint: Satisfy the left-neighbour rule in one pass and the right-neighbour rule in another, then keep the larger requirement for each child.

  9. Solve Merge Intervals (opens in a new tab) (LeetCode, medium)

    Hint: Sort by start so overlaps become neighbours. Then keep stretching the last output interval while the next one starts at or before its end.

  10. Solve Insert Interval (opens in a new tab) (LeetCode, medium)

    Hint: The list is already sorted. Copy everything that ends before the new one, merge everything that overlaps it, then copy the rest.

Additional resources