LeetCode Patterns ·

🎯 Greedy Algorithms

1️⃣ Core Framework

When discussing Greedy Algorithms, I frame it as:

What problem pattern greedy solves
Local optimum vs global optimum
Greedy choice property
Sorting-based greedy
Interval greedy
Two-pointer greedy
Heap greedy
Counterexamples
Common edge cases
Senior-level explanation

2️⃣ What Problem Are We Solving?

Greedy algorithms are used when we can make the best local decision at each step and still reach a globally optimal answer.

They are commonly used for:

Interval scheduling
Jump Game
Gas Station
Assign Cookies
Merge intervals variants
Non-overlapping intervals
Minimum arrows to burst balloons
Task scheduling
Huffman coding
Meeting rooms
Stock buy/sell simple variants
Partition Labels

The core idea is:

At each step,
make the best immediate choice,
and never revisit that decision.

👉 Interview Answer

A greedy algorithm makes the locally best choice at each step.

It works only when local optimal decisions can lead to a globally optimal solution.

The key is to prove why the greedy choice is safe, usually through an exchange argument or by showing that delaying or changing the choice cannot improve the answer.

3️⃣ Greedy vs Dynamic Programming

Greedy

Greedy chooses once:

make local best choice
move forward
do not revisit

Good when:

local choice is always safe

Dynamic Programming

DP explores multiple choices:

try choices
store subproblem answers
reuse results

Good when:

local choice may not be enough
overlapping subproblems exist

Key Difference

Pattern	Decision Style	Revisit Choices?
Greedy	Local best choice	No
DP	Explore and compare choices	Yes

👉 Interview Answer

Greedy and DP both solve optimization problems, but they differ in how they handle choices.

Greedy commits to one local decision and does not revisit it.

DP keeps track of multiple subproblem results and compares choices.

If a local decision can be proven safe, greedy is simpler and faster.

If not, DP is usually safer.

4️⃣ Greedy Choice Property

What It Means

A problem has greedy choice property if:

there exists an optimal solution that includes the greedy choice

This means we can safely make the greedy choice first.

Example

Interval scheduling:

choose the interval that ends earliest

Why?

The earlier an interval ends, the more room remains for future intervals.

Key Requirement

We need a reason why the local choice does not block a better global solution.

👉 Interview Answer

The greedy choice property means that there is always an optimal solution containing the greedy choice.

Once we prove that, we can safely make that choice and reduce the problem.

Without that property, greedy may produce a locally good but globally bad result.

5️⃣ Exchange Argument

What Is Exchange Argument?

An exchange argument proves greedy correctness by showing:

If an optimal solution does not use the greedy choice,
we can replace part of that solution with the greedy choice
without making the solution worse.

Example: Earliest Ending Interval

Suppose the optimal solution chooses interval X first.

Greedy chooses interval G that ends earlier than or equal to X.

We can replace X with G.

This does not reduce the number of intervals we can schedule, because G leaves at least as much remaining time as X.

👉 Interview Answer

An exchange argument is a common way to prove greedy correctness.

I compare the greedy choice with the first choice in an optimal solution.

If I can replace the optimal solution’s choice with the greedy choice without making the result worse, then the greedy choice is safe.

6️⃣ Sorting-Based Greedy

Common Pattern

Many greedy problems start by sorting.

Sort by:

start time
end time
deadline
size
cost
profit
frequency

The sorting key usually exposes the safe local choice.

Examples

Interval scheduling: sort by end time
Assign cookies: sort children and cookies
Minimum arrows: sort balloons by end
Meeting rooms: sort start and end times

👉 Interview Answer

Many greedy problems rely on sorting first.

The sorting order determines which local choice becomes safe.

For interval problems, sorting by end time is common because finishing earlier preserves more future options.

For matching problems, sorting both sides often helps pair small requirements with small resources.

7️⃣ Assign Cookies

Problem

Each child has a greed factor. Each cookie has a size. A child is satisfied if cookie size is at least the greed factor.

Return the maximum number of satisfied children.

Greedy Idea

Sort both arrays.

Use the smallest cookie that can satisfy the least greedy child.

Code

def find_content_children(g, s):
    g.sort()
    s.sort()

    child = 0
    cookie = 0

    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1

        cookie += 1

    return child

👉 Interview Answer

For Assign Cookies, I sort children by greed and cookies by size.

I try to satisfy the least greedy child using the smallest possible cookie.

If a cookie is too small, it cannot satisfy this child or any greedier child, so I discard it.

This greedy choice maximizes the number of satisfied children.

8️⃣ Jump Game

Problem

Given an array where each element is the maximum jump length from that index, determine whether we can reach the last index.

Greedy Idea

Track the farthest reachable index.

If current index is beyond farthest:

return False

Otherwise, update:

farthest = max(farthest, i + nums[i])

Code

def can_jump(nums):
    farthest = 0

    for i, jump in enumerate(nums):
        if i > farthest:
            return False

        farthest = max(farthest, i + jump)

    return True

👉 Interview Answer

For Jump Game, I track the farthest index reachable so far.

If I reach an index greater than farthest, that index is unreachable and the answer is false.

Otherwise, I use the current jump length to expand farthest.

If the scan finishes, the last index is reachable.

9️⃣ Jump Game II

Problem

Return the minimum number of jumps needed to reach the last index.

Greedy Idea

Think of the current jump as covering a range.

Within the current range, find the farthest next reach.

When we reach the end of the current range, we must make another jump.

Code

def jump(nums):
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

👉 Interview Answer

For Jump Game II, I use a level-based greedy approach.

current_end represents the farthest index reachable with the current number of jumps.

farthest represents the farthest index reachable with one more jump.

When I reach current_end, I must increase the jump count and move to the next range.

🔟 Gas Station

Problem

There are gas stations in a circle. Each station has gas[i]. Traveling to the next station costs cost[i].

Return the start index if we can complete the circuit, otherwise return -1.

Greedy Insight

If total gas is less than total cost:

impossible

If the current tank becomes negative at index i, then no station between the current start and i can be a valid start.

So start from:

i + 1

Code

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1

    start = 0
    tank = 0

    for i in range(len(gas)):
        tank += gas[i] - cost[i]

        if tank < 0:
            start = i + 1
            tank = 0

    return start

👉 Interview Answer

For Gas Station, first I check whether total gas is at least total cost.

If not, no solution exists.

Then I scan stations while maintaining current tank.

If tank becomes negative at station i, the current start and every station before i cannot be valid.

So I reset the start to i + 1.

1️⃣1️⃣ Interval Scheduling

Problem

Given intervals, select the maximum number of non-overlapping intervals.

Greedy Idea

Sort intervals by end time.

Always pick the interval that ends earliest.

Code

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])

    count = 0
    end = float("-inf")

    for start, finish in intervals:
        if start >= end:
            count += 1
            end = finish

    return count

👉 Interview Answer

For selecting the maximum number of non-overlapping intervals, I sort intervals by end time.

I always choose the interval that finishes earliest among available choices.

This leaves the most room for future intervals, which makes the greedy choice safe.

1️⃣2️⃣ Non-overlapping Intervals

Problem

Given intervals, return the minimum number of intervals to remove so the rest are non-overlapping.

Greedy Idea

Equivalent to:

keep the maximum number of non-overlapping intervals

Then:

removals = total - kept

Code

def erase_overlap_intervals(intervals):
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])

    kept = 0
    end = float("-inf")

    for start, finish in intervals:
        if start >= end:
            kept += 1
            end = finish

    return len(intervals) - kept

👉 Interview Answer

Non-overlapping Intervals can be solved by keeping as many non-overlapping intervals as possible.

I sort by end time and greedily keep intervals that do not overlap with the last kept interval.

The minimum removals equals total intervals minus kept intervals.

1️⃣3️⃣ Minimum Arrows to Burst Balloons

Problem

Each balloon is represented by an interval. One arrow shot at position x bursts all balloons whose interval contains x.

Return the minimum number of arrows needed.

Greedy Idea

Sort by end coordinate.

Shoot an arrow at the end of the first balloon.

This bursts as many overlapping balloons as possible.

Code

def find_min_arrow_shots(points):
    if not points:
        return 0

    points.sort(key=lambda x: x[1])

    arrows = 1
    arrow_pos = points[0][1]

    for start, end in points[1:]:
        if start > arrow_pos:
            arrows += 1
            arrow_pos = end

    return arrows

👉 Interview Answer

For Minimum Arrows, I sort balloons by ending coordinate.

I shoot the arrow at the end of the first balloon.

Any balloon starting before or at that position is burst by the same arrow.

If the next balloon starts after the arrow position, I need a new arrow.

1️⃣4️⃣ Merge Intervals vs Greedy Selection

Merge Intervals

Goal:

combine overlapping intervals

Sort by start.

Interval Selection

Goal:

choose maximum non-overlapping intervals

Sort by end.

Key Difference

Problem	Goal	Sort By
Merge Intervals	Combine overlaps	Start
Non-overlapping selection	Keep as many as possible	End
Minimum arrows	Cover intervals with points	End

👉 Interview Answer

Interval problems look similar, but the sorting key depends on the goal.

If I need to merge intervals, I usually sort by start.

If I need to select the maximum number of non-overlapping intervals, I usually sort by end.

Sorting by end preserves the most future options.

1️⃣5️⃣ Partition Labels

Problem

Partition a string into as many parts as possible so that each letter appears in at most one part.

Greedy Idea

First record the last occurrence of each character.

Scan the string and maintain the farthest last occurrence of all characters seen so far.

When current index reaches that farthest boundary, we can close a partition.

Code

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}

    result = []
    start = 0
    end = 0

    for i, ch in enumerate(s):
        end = max(end, last[ch])

        if i == end:
            result.append(end - start + 1)
            start = i + 1

    return result

👉 Interview Answer

For Partition Labels, I record the last occurrence of each character.

While scanning, I maintain the farthest last occurrence of all characters in the current partition.

When the current index reaches that farthest point, the partition can safely close.

1️⃣6️⃣ Best Time to Buy and Sell Stock II

Problem

You may complete as many transactions as you want, but you must sell before buying again.

Return maximum profit.

Greedy Idea

Take every positive price difference.

If price increases from one day to the next, capture that profit.

Code

def max_profit(prices):
    profit = 0

    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]

    return profit

👉 Interview Answer

For Stock II, every upward price movement can be taken as profit.

Adding all positive differences gives the same result as buying at each valley and selling at each peak.

Because unlimited transactions are allowed, this greedy strategy is optimal.

1️⃣7️⃣ Lemonade Change

Problem

Customers buy lemonade for $5. Each pays with $5, $10, or $20. Return whether we can give correct change to every customer.

Greedy Idea

For a $20 bill, prefer giving:

$10 + $5

instead of:

$5 + $5 + $5

because $5 bills are more flexible.

Code

def lemonade_change(bills):
    five = 0
    ten = 0

    for bill in bills:
        if bill == 5:
            five += 1

        elif bill == 10:
            if five == 0:
                return False
            five -= 1
            ten += 1

        else:
            if ten > 0 and five > 0:
                ten -= 1
                five -= 1
            elif five >= 3:
                five -= 3
            else:
                return False

    return True

👉 Interview Answer

For Lemonade Change, I greedily preserve smaller bills because they are more flexible.

When giving change for $20, I prefer using one $10 and one $5 if possible.

Otherwise, I use three $5 bills.

If neither is possible, return false.

1️⃣8️⃣ Task Scheduler

Problem

Given tasks and a cooldown interval n, return the minimum time needed to finish all tasks.

Greedy Insight

The most frequent task determines the base structure.

If max frequency is:

max_freq

Then we need:

max_freq - 1

full gaps between its occurrences.

Each gap has size:

n + 1

If multiple tasks share max frequency, they occupy the final slots together.

Formula

max(
    len(tasks),
    (max_freq - 1) * (n + 1) + count_max
)

Code

from collections import Counter

def least_interval(tasks, n):
    freq = Counter(tasks)

    max_freq = max(freq.values())
    count_max = sum(1 for v in freq.values() if v == max_freq)

    return max(
        len(tasks),
        (max_freq - 1) * (n + 1) + count_max
    )

👉 Interview Answer

For Task Scheduler, the most frequent task determines the minimum structure.

I create blocks around the most frequent task, then fill idle slots with other tasks.

The final answer is the larger of total task count and the block-based lower bound.

1️⃣9️⃣ Heap-Based Greedy

When Heap Is Useful

Use a heap when the greedy choice depends on the current best available item.

Common examples:

always choose largest frequency
always choose smallest end time
always choose cheapest available option
always choose highest profit among available projects

Examples

Task Scheduler simulation
Reorganize String
IPO
Meeting Rooms II
K Closest style greedy variants

👉 Interview Answer

Heap-based greedy is useful when the best local choice changes over time.

A heap lets us repeatedly choose the current minimum or maximum candidate efficiently.

This is common in scheduling, frequency-based problems, and resource allocation.

2️⃣0️⃣ Reorganize String

Problem

Rearrange a string so that no two adjacent characters are the same.

Return any valid string or empty string if impossible.

Greedy Idea

Always pick the character with the highest remaining frequency, but avoid using the same character as the previous one.

Use a max heap.

Code

from collections import Counter
import heapq

def reorganize_string(s):
    freq = Counter(s)

    heap = [(-count, ch) for ch, count in freq.items()]
    heapq.heapify(heap)

    result = []
    prev_count = 0
    prev_ch = ""

    while heap:
        count, ch = heapq.heappop(heap)
        result.append(ch)

        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_ch))

        count += 1

        prev_count = count
        prev_ch = ch

    answer = "".join(result)

    if len(answer) != len(s):
        return ""

    return answer

👉 Interview Answer

For Reorganize String, I use a max heap to always choose the character with the highest remaining frequency.

After using a character, I temporarily hold it out for one round, so it cannot be placed adjacent to itself.

If we cannot build a full-length result, no valid arrangement exists.

2️⃣1️⃣ Greedy Proof Checklist

Questions to Ask

Before trusting greedy, ask:

What is the local choice?
Why is it safe?
Can I exchange an optimal solution's choice with my greedy choice?
Does the greedy choice preserve future options?
Can I construct a counterexample?

Important

Greedy is often easy to code but hard to prove.

The proof matters in interviews.

👉 Interview Answer

For greedy problems, I do not only explain the implementation.

I explain why the local choice is safe.

Usually I use an exchange argument, or I explain how the choice preserves the most future options.

If I cannot justify the choice, I consider DP instead.

2️⃣2️⃣ Common Edge Cases

Empty Input

intervals = []
prices = []
tasks = []

Single Element

one interval
one task
one price

Already Optimal

already non-overlapping
already reachable
already sorted

Impossible Case

cannot reach end
not enough change
not enough gas
reorganization impossible

Ties

When multiple choices are equally good, make sure tie-breaking does not break correctness.

👉 Interview Answer

Common greedy edge cases include empty input, single element, impossible cases, already optimal input, and ties between choices.

I pay attention to whether ties require special handling or whether any tied choice is safe.

2️⃣3️⃣ Common Mistakes

Mistake 1: Assuming Greedy Without Proof

A local best choice is not always globally best.

Mistake 2: Wrong Sorting Key

Interval problems often fail because of sorting by start instead of end.

Mistake 3: Confusing Merge and Selection

Merge intervals and interval scheduling use different strategies.

Mistake 4: Missing Impossible Check

Examples:

total gas < total cost
reorganize string max frequency too high

Mistake 5: Not Handling Ties

Some problems require careful tie handling.

Mistake 6: Using Greedy Where DP Is Needed

If choices interact in complex ways, DP may be required.

👉 Interview Answer

Common greedy mistakes include assuming greedy without proof, choosing the wrong sorting key, confusing merge intervals with interval selection, missing impossible checks, mishandling ties, and using greedy when DP is required.

I always try to justify why the local choice is safe.

2️⃣4️⃣ When Greedy Applies

Good Fit

Use greedy when:

local best choice is safe
problem has greedy choice property
sorting exposes a natural order
choosing earliest ending preserves future options
choosing smallest sufficient resource is optimal
choosing farthest reach is optimal

Problem Signals

Look for words like:

minimum number
maximum number
schedule
interval
deadline
reach farthest
assign resources
remove fewest
cover intervals

👉 Interview Answer

I consider greedy when the problem asks for an optimal value and there appears to be a safe local choice.

Common signs include interval scheduling, resource assignment, farthest reach, earliest finish time, and choosing the smallest sufficient resource.

2️⃣5️⃣ When Greedy Does Not Apply

Not Good Fit

Greedy may fail when:

local choice can block a better future solution
choices have complex dependencies
there are overlapping subproblems
need exact optimal under many interacting constraints
need all solutions

Better Alternatives

Problem Type	Better Pattern
Overlapping subproblems	Dynamic Programming
Need all solutions	Backtracking
Shortest path unweighted	BFS
Weighted shortest path	Dijkstra
Connectivity	DFS / Union Find
Range queries	Prefix Sum / Segment Tree

👉 Interview Answer

Greedy does not apply when a locally optimal choice can block a better global solution.

If choices interact in a way that requires comparing multiple future states, DP is usually more appropriate.

If the problem asks for all solutions, backtracking is usually better.

2️⃣6️⃣ Standard Templates

Sorting Greedy Template

def greedy_sort(items):
    items.sort(key=lambda x: greedy_key(x))

    answer = initial_value

    for item in items:
        if can_take(item):
            take(item)
            update_answer()

    return answer

Interval End-Time Template

def interval_greedy(intervals):
    intervals.sort(key=lambda x: x[1])

    count = 0
    end = float("-inf")

    for start, finish in intervals:
        if start >= end:
            count += 1
            end = finish

    return count

Farthest Reach Template

def farthest_reach(nums):
    farthest = 0

    for i, jump in enumerate(nums):
        if i > farthest:
            return False

        farthest = max(farthest, i + jump)

    return True

Range Jump Template

def min_jumps(nums):
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

Heap Greedy Template

import heapq

def heap_greedy(items):
    heap = []

    for item in items:
        heapq.heappush(heap, transform(item))

    answer = []

    while heap:
        best = heapq.heappop(heap)
        process(best, answer)

    return answer

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

A greedy algorithm makes the locally best decision at each step and commits to it.

It is appropriate only when that local decision can be proven to lead to a globally optimal solution.

The key property is the greedy choice property: there exists an optimal solution that includes the greedy choice.

A common way to prove this is an exchange argument. If an optimal solution does not use the greedy choice, we show that we can replace part of that optimal solution with the greedy choice without making the answer worse.

Many greedy problems start with sorting. The sorting key is critical. For interval scheduling, sorting by end time works because choosing the earliest ending interval leaves the most room for future intervals. For resource assignment problems, sorting both requirements and resources often lets us match the smallest sufficient resource to the smallest need.

Some greedy problems are based on reachability. In Jump Game, we track the farthest reachable index. If we ever reach an index beyond farthest, the end is impossible. In Jump Game II, we treat reachable indexes as ranges and increase the jump count when the current range ends.

Some greedy problems need a global feasibility check. In Gas Station, if total gas is less than total cost, no start can work. Otherwise, if the current tank becomes negative, all stations in the failed segment cannot be valid starts.

Some greedy problems use a heap. A heap is useful when the best available choice changes dynamically, such as always picking the highest frequency task, earliest ending meeting, or cheapest available option.

The biggest risk with greedy is assuming it works without proof. A local optimum is not always a global optimum. If I cannot justify the greedy choice, I consider dynamic programming or backtracking instead.

At a senior level, I would explain: what the local greedy choice is, why it is safe, what invariant it maintains, whether sorting or heap is needed, how impossible cases are detected, and why a counterexample cannot break the strategy.

⭐ Final Insight

Greedy 的核心不是“每一步选看起来最好的”。

它的核心是证明这个 local choice 是 safe 的。

Senior-level 的重点是：

greedy choice 是什么，为什么这个选择不会破坏 future options，是否能用 exchange argument 证明， sorting key 为什么正确， invariant 是什么，以及什么时候 greedy 会失败、需要换成 DP。

能讲清楚这些， Greedy 就不是猜答案，而是一种基于 safe local decision 的优化策略。

中文部分

🎯 Greedy Algorithms

1️⃣ 核心框架

讨论 Greedy Algorithms 时，我通常从：

Greedy 解决什么问题
Local optimum vs global optimum
Greedy choice property
Sorting-based greedy
Interval greedy
Two-pointer greedy
Heap greedy
Counterexamples
常见 edge cases
高级工程师解释方式

2️⃣ 要解决什么问题？

Greedy algorithms 用于每一步做局部最优选择，并且这个选择最终能够得到全局最优答案的场景。

它常用于：

Interval scheduling
Jump Game
Gas Station
Assign Cookies
Merge intervals variants
Non-overlapping intervals
Minimum arrows to burst balloons
Task scheduling
Huffman coding
Meeting rooms
Stock buy/sell simple variants
Partition Labels

核心思想是：

每一步都做当前最好的选择，
并且之后不回头修改这个选择。

👉 面试回答

Greedy algorithm 是每一步选择当前看起来最优的 decision。

它只有在 local optimal decision 能推出 global optimal answer 时才正确。

关键不是代码，而是证明为什么这个 greedy choice 是 safe 的。

通常可以用 exchange argument 或 invariant 来说明。

3️⃣ Greedy vs Dynamic Programming

Greedy

Greedy 做一次选择：

make local best choice
move forward
do not revisit

适合：

local choice is always safe

Dynamic Programming

DP 会比较多个选择：

try choices
store subproblem answers
reuse results

适合：

local choice may not be enough
overlapping subproblems exist

Key Difference

Pattern	Decision Style	Revisit Choices?
Greedy	Local best choice	No
DP	Explore and compare choices	Yes

👉 面试回答

Greedy 和 DP 都可以解决 optimization problem。

但 greedy 会直接 commit 一个 local decision，不再回头。

DP 会保留多个 subproblem 的结果，并比较不同选择。

如果 local choice 可以证明 safe， greedy 通常更简单更快。

如果不能证明， DP 通常更安全。

4️⃣ Greedy Choice Property

What It Means

如果一个问题有 greedy choice property，表示：

存在一个 optimal solution 包含 greedy choice

这说明我们可以安全地先做这个 greedy choice。

Example

Interval scheduling:

choose the interval that ends earliest

为什么？

因为结束越早，留给后面 intervals 的空间越多。

Key Requirement

需要解释为什么 local choice 不会阻碍更好的 global solution。

👉 面试回答

Greedy choice property 表示：存在一个 optimal solution 包含我们当前做出的 greedy choice。

一旦证明这一点，就可以安全地做这个选择，并把问题缩小。

如果没有这个性质， greedy 可能得到 local best，但不是 global best。

5️⃣ Exchange Argument

什么是 Exchange Argument？

Exchange argument 用来证明 greedy correctness。

它的核心是：

如果某个 optimal solution 没有使用 greedy choice，
我们可以把它的一部分替换成 greedy choice，
并且答案不会变差。

Example: Earliest Ending Interval

假设 optimal solution 第一个选择 interval X。

Greedy 选择 interval G，并且 G 的结束时间不晚于 X。

我们可以用 G 替换 X。

因为 G 结束更早或一样早，所以给后面 intervals 留出的空间不会更少。

👉 面试回答

Exchange argument 是证明 greedy 正确性的常见方法。

我会把 greedy choice 和某个 optimal solution 中的选择比较。

如果可以把 optimal solution 的选择替换成 greedy choice，且不会让结果变差，那就说明 greedy choice 是 safe 的。

6️⃣ Sorting-Based Greedy

Common Pattern

很多 greedy 问题都先 sort。

常见排序维度：

start time
end time
deadline
size
cost
profit
frequency

Sorting key 通常暴露了安全的 local choice。

Examples

Interval scheduling: sort by end time
Assign cookies: sort children and cookies
Minimum arrows: sort balloons by end
Meeting rooms: sort start and end times

👉 面试回答

很多 greedy 问题依赖 sorting。

Sorting order 决定了哪个 local choice 是 safe 的。

对 interval problems，按 end time 排序很常见，因为越早结束越能保留 future options。

对 matching problems，排序 requirements 和 resources 后，通常可以用最小 sufficient resource 去满足最小需求。

7️⃣ Assign Cookies

Problem

每个 child 有 greed factor。每个 cookie 有 size。如果 cookie size 至少等于 greed factor， child 就 satisfied。

返回最多能 satisfy 的 children 数量。

Greedy Idea

两个数组都排序。

用能满足当前 least greedy child 的最小 cookie。

Code

def find_content_children(g, s):
    g.sort()
    s.sort()

    child = 0
    cookie = 0

    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1

        cookie += 1

    return child

👉 面试回答

对 Assign Cookies，我先把 children 的 greed 和 cookies 的 size 都排序。

然后用最小可行 cookie 去满足当前最不贪心的 child。

如果当前 cookie 太小，它也不可能满足更贪心的 child，所以直接跳过。

这个策略可以最大化 satisfied children 数量。

8️⃣ Jump Game

Problem

给定 array，每个 element 表示从该 index 能跳的 maximum length。判断是否能到达 last index。

Greedy Idea

维护 farthest reachable index。

如果当前 index 超过 farthest：

return False

否则更新：

farthest = max(farthest, i + nums[i])

Code

def can_jump(nums):
    farthest = 0

    for i, jump in enumerate(nums):
        if i > farthest:
            return False

        farthest = max(farthest, i + jump)

    return True

👉 面试回答

对 Jump Game，我维护目前能到达的最远 index。

如果扫描到的 index 已经超过 farthest，说明这个位置无法到达，返回 false。

否则用当前 jump length 更新 farthest。

如果整个数组扫描完成，说明 last index 可达。

9️⃣ Jump Game II

Problem

返回到达 last index 所需的 minimum jumps。

Greedy Idea

把当前 jump 能覆盖的 index 看成一个 range。

在当前 range 中，找到下一跳能到达的最远位置。

当扫描到当前 range 的末尾时，必须增加一次 jump。

Code

def jump(nums):
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

👉 面试回答

对 Jump Game II，我用类似 BFS level 的 greedy。

current_end 表示当前 jumps 数量可以覆盖到的最远 index。

farthest 表示再跳一次能覆盖到的最远 index。

当 i 到达 current_end，说明必须增加一次 jump，并把 current_end 更新为 farthest。

🔟 Gas Station

Problem

有一圈 gas stations。每个 station 有 gas[i]。从 i 到 i + 1 需要 cost[i]。

如果能绕一圈，返回 start index；否则返回 -1。

Greedy Insight

如果 total gas 小于 total cost：

impossible

如果从当前 start 出发，到 index i 时 tank 变成 negative，那么从 current start 到 i 中间任何 station 出发都不可能成功。

所以新的 start 是：

i + 1

Code

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1

    start = 0
    tank = 0

    for i in range(len(gas)):
        tank += gas[i] - cost[i]

        if tank < 0:
            start = i + 1
            tank = 0

    return start

👉 面试回答

对 Gas Station，我先检查 total gas 是否至少等于 total cost。

如果不是，任何 start 都不可能。

然后扫描 stations 并维护当前 tank。

如果 tank 在 index i 变成 negative，当前 start 到 i 之间的所有位置都不能作为 valid start。

所以把 start 重置为 i + 1。

1️⃣1️⃣ Interval Scheduling

Problem

给定 intervals，选择最多数量的 non-overlapping intervals。

Greedy Idea

按 end time 排序。

每次选择结束最早的 interval。

Code

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])

    count = 0
    end = float("-inf")

    for start, finish in intervals:
        if start >= end:
            count += 1
            end = finish

    return count

👉 面试回答

对选择最多 non-overlapping intervals，我会按 end time 排序。

每次选择当前能选的、结束最早的 interval。

因为它给后续 intervals 留出最多空间，所以这是 safe greedy choice。

1️⃣2️⃣ Non-overlapping Intervals

Problem

给定 intervals，返回最少需要 remove 多少 intervals，才能让剩下 intervals 不重叠。

Greedy Idea

等价于：

保留最多数量的 non-overlapping intervals

然后：

removals = total - kept

Code

def erase_overlap_intervals(intervals):
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])

    kept = 0
    end = float("-inf")

    for start, finish in intervals:
        if start >= end:
            kept += 1
            end = finish

    return len(intervals) - kept

👉 面试回答

Non-overlapping Intervals 可以转化成：尽量保留最多 non-overlapping intervals。

我按 end time 排序，贪心保留不和上一个保留 interval 重叠的 interval。

最少删除数量就是 total intervals 减去 kept intervals。

1️⃣3️⃣ Minimum Arrows to Burst Balloons

Problem

每个 balloon 是一个 interval。一支 arrow 射在位置 x，可以 burst 所有包含 x 的 balloons。

返回最少 arrow 数量。

Greedy Idea

按 end coordinate 排序。

第一支 arrow 射在第一个 balloon 的 end。

这样可以覆盖尽可能多的 overlapping balloons。

Code

def find_min_arrow_shots(points):
    if not points:
        return 0

    points.sort(key=lambda x: x[1])

    arrows = 1
    arrow_pos = points[0][1]

    for start, end in points[1:]:
        if start > arrow_pos:
            arrows += 1
            arrow_pos = end

    return arrows

👉 面试回答

对 Minimum Arrows，我按 balloon 的 end coordinate 排序。

第一支 arrow 放在最早结束 balloon 的 end。

所有 start 小于等于这个 arrow position 的 balloons 都能被同一支 arrow burst。

如果下一个 balloon 的 start 大于 arrow position，就必须再用一支 arrow。

1️⃣4️⃣ Merge Intervals vs Greedy Selection

Merge Intervals

目标是：

combine overlapping intervals

通常按 start 排序。

Interval Selection

目标是：

choose maximum non-overlapping intervals

通常按 end 排序。

Key Difference

Problem	Goal	Sort By
Merge Intervals	Combine overlaps	Start
Non-overlapping selection	Keep as many as possible	End
Minimum arrows	Cover intervals with points	End

👉 面试回答

Interval problems 看起来相似，但 sorting key 取决于目标。

如果目标是 merge intervals，我通常按 start 排序。

如果目标是选择最多 non-overlapping intervals，我通常按 end 排序。

End time 越早，给后面留下的空间越大。

1️⃣5️⃣ Partition Labels

Problem

把 string 分成尽可能多的 parts，使得每个 letter 最多只出现在一个 part 中。

Greedy Idea

先记录每个 character 最后出现的位置。

扫描字符串，维护当前 partition 中所有 characters 的最远 last occurrence。

当当前 index 到达这个边界时，当前 partition 可以关闭。

Code

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}

    result = []
    start = 0
    end = 0

    for i, ch in enumerate(s):
        end = max(end, last[ch])

        if i == end:
            result.append(end - start + 1)
            start = i + 1

    return result

👉 面试回答

对 Partition Labels，我先记录每个 character 的 last occurrence。

扫描过程中，维护当前 partition 必须覆盖到的最远 index。

当当前 i 到达这个最远边界，说明当前 partition 中所有字符都不会在后面出现，所以可以安全切分。

1️⃣6️⃣ Best Time to Buy and Sell Stock II

Problem

可以完成任意多次 transactions，但必须先 sell 再 buy。

返回 maximum profit。

Greedy Idea

累加所有 positive price difference。

如果明天比今天贵，就把这段上涨 profit 收集起来。

Code

def max_profit(prices):
    profit = 0

    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]

    return profit

👉 面试回答

对 Stock II，每一段上涨都可以转化成 profit。

累加所有 positive differences，等价于在每个 valley 买入、每个 peak 卖出。

因为 transactions 没有限制，这个 greedy strategy 是 optimal 的。

1️⃣7️⃣ Lemonade Change

Problem

顾客买 $5 lemonade。每个顾客支付 $5、$10 或 $20。判断是否能给每个顾客正确找零。

Greedy Idea

对于 $20 找零，优先使用：

$10 + $5

而不是：

$5 + $5 + $5

因为 $5 bills 更灵活。

Code

def lemonade_change(bills):
    five = 0
    ten = 0

    for bill in bills:
        if bill == 5:
            five += 1

        elif bill == 10:
            if five == 0:
                return False
            five -= 1
            ten += 1

        else:
            if ten > 0 and five > 0:
                ten -= 1
                five -= 1
            elif five >= 3:
                five -= 3
            else:
                return False

    return True

👉 面试回答

对 Lemonade Change，我会 greedy 地保留更多 $5 bills，因为 $5 是最灵活的找零单位。

对 $20 找零时，如果可以用 $10 + $5，就优先这样找。

否则再用三个 $5。

如果都不行，返回 false。

1️⃣8️⃣ Task Scheduler

Problem

给定 tasks 和 cooldown interval n，返回完成所有 tasks 的 minimum time。

Greedy Insight

出现次数最多的 task 决定基本结构。

如果 max frequency 是：

max_freq

那么需要：

max_freq - 1

个完整 gaps。

每个 gap 大小是：

n + 1

如果多个 tasks 都有 max frequency，它们一起占据最后一组 slots。

Formula

max(
    len(tasks),
    (max_freq - 1) * (n + 1) + count_max
)

Code

from collections import Counter

def least_interval(tasks, n):
    freq = Counter(tasks)

    max_freq = max(freq.values())
    count_max = sum(1 for v in freq.values() if v == max_freq)

    return max(
        len(tasks),
        (max_freq - 1) * (n + 1) + count_max
    )

👉 面试回答

对 Task Scheduler，出现频率最高的 task 决定了最少需要的基本框架。

我先用最高频 task 构造 blocks，再用其他 tasks 填充 idle slots。

最终答案是 task 总数量和 block-based lower bound 中的较大值。

1️⃣9️⃣ Heap-Based Greedy

When Heap Is Useful

当 greedy choice 是动态变化的 current best candidate， heap 很有用。

常见场景：

always choose largest frequency
always choose smallest end time
always choose cheapest available option
always choose highest profit among available projects

Examples

Task Scheduler simulation
Reorganize String
IPO
Meeting Rooms II
K Closest style greedy variants

👉 面试回答

Heap-based greedy 适合 best available choice 会动态变化的场景。

Heap 可以让我们高效地反复取出当前最小或最大的 candidate。

这常见于 scheduling、frequency-based problems 和 resource allocation。

2️⃣0️⃣ Reorganize String

Problem

重新排列 string，让相邻两个 characters 不相同。

如果不可能，返回 empty string。

Greedy Idea

每次选择剩余频率最高的 character，但不能让它和上一个 character 相同。

使用 max heap。

Code

from collections import Counter
import heapq

def reorganize_string(s):
    freq = Counter(s)

    heap = [(-count, ch) for ch, count in freq.items()]
    heapq.heapify(heap)

    result = []
    prev_count = 0
    prev_ch = ""

    while heap:
        count, ch = heapq.heappop(heap)
        result.append(ch)

        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_ch))

        count += 1

        prev_count = count
        prev_ch = ch

    answer = "".join(result)

    if len(answer) != len(s):
        return ""

    return answer

👉 面试回答

对 Reorganize String，我使用 max heap，每次选择剩余 frequency 最高的 character。

使用某个 character 后，我会暂时把它 hold out 一轮，防止它马上再次被使用导致相邻重复。

如果最后构造出的长度不等于原 string，说明不存在 valid arrangement。

2️⃣1️⃣ Greedy Proof Checklist

Questions to Ask

写 greedy 前先问：

Local choice 是什么？
为什么它 safe？
能不能用 exchange argument？
这个选择是否保留 future options？
有没有 counterexample？

Important

Greedy 经常代码简单，但证明更重要。

👉 面试回答

对 greedy 问题，我不会只解释 implementation。

我会解释为什么 local choice 是 safe 的。

通常我会使用 exchange argument，或说明这个选择如何保留最多 future options。

如果无法证明，我会考虑 DP。

2️⃣2️⃣ 常见 Edge Cases

Empty Input

intervals = []
prices = []
tasks = []

Single Element

one interval
one task
one price

Already Optimal

already non-overlapping
already reachable
already sorted

Impossible Case

cannot reach end
not enough change
not enough gas
reorganization impossible

Ties

当多个 choices 一样好时，需要确认 tie-breaking 不会影响 correctness。

👉 面试回答

Greedy 常见 edge cases 包括 empty input、 single element、 impossible cases、 already optimal input、以及 ties。

我会注意 tie-breaking 是否需要特殊处理，或者任意 tied choice 是否都是 safe 的。

2️⃣3️⃣ 常见错误

Mistake 1: 没有证明就假设 Greedy 正确

Local best 不一定等于 global best。

Mistake 2: Sorting Key 错误

Interval problems 经常因为按 start 排而不是 end 排导致错误。

Mistake 3: 混淆 Merge 和 Selection

Merge intervals 和 interval scheduling 用的策略不同。

Mistake 4: 忘记 Impossible Check

Examples:

total gas < total cost
reorganize string max frequency too high

Mistake 5: Tie Handling 错误

有些题 tie 需要小心处理。

Mistake 6: 该用 DP 却用了 Greedy

如果 choices 之间有复杂依赖，通常需要 DP。

👉 面试回答

Greedy 常见错误包括：没有证明就假设 greedy 正确、 sorting key 错误、混淆 merge intervals 和 interval selection、忘记 impossible checks、 tie handling 错误、以及在需要 DP 的问题上强行 greedy。

我通常会先说明：为什么当前 local choice 是 safe 的。

2️⃣4️⃣ 什么时候 Greedy 适用？

Good Fit

当问题满足：

local best choice is safe
problem has greedy choice property
sorting exposes a natural order
choosing earliest ending preserves future options
choosing smallest sufficient resource is optimal
choosing farthest reach is optimal

Problem Signals

看到这些关键词想到 greedy：

minimum number
maximum number
schedule
interval
deadline
reach farthest
assign resources
remove fewest
cover intervals

👉 面试回答

当问题要求 optimal value，并且存在一个可以证明 safe 的 local choice 时，我会考虑 greedy。

常见信号包括 interval scheduling、 resource assignment、 farthest reach、 earliest finish time、以及 smallest sufficient resource。

2️⃣5️⃣ 什么时候 Greedy 不适用？

Not Good Fit

Greedy 可能失败，如果：

local choice can block a better future solution
choices have complex dependencies
there are overlapping subproblems
need exact optimal under many interacting constraints
need all solutions

Better Alternatives

Problem Type	Better Pattern
Overlapping subproblems	Dynamic Programming
Need all solutions	Backtracking
Shortest path unweighted	BFS
Weighted shortest path	Dijkstra
Connectivity	DFS / Union Find
Range queries	Prefix Sum / Segment Tree

👉 面试回答

如果 local optimal choice 可能阻碍更好的 global solution， greedy 就不适合。

如果 choices 之间有复杂依赖，需要比较多个 future states， DP 通常更合适。

如果题目要求所有 solutions， backtracking 通常更合适。

2️⃣6️⃣ 标准模板

Sorting Greedy Template

def greedy_sort(items):
    items.sort(key=lambda x: greedy_key(x))

    answer = initial_value

    for item in items:
        if can_take(item):
            take(item)
            update_answer()

    return answer

Interval End-Time Template

def interval_greedy(intervals):
    intervals.sort(key=lambda x: x[1])

    count = 0
    end = float("-inf")

    for start, finish in intervals:
        if start >= end:
            count += 1
            end = finish

    return count

Farthest Reach Template

def farthest_reach(nums):
    farthest = 0

    for i, jump in enumerate(nums):
        if i > farthest:
            return False

        farthest = max(farthest, i + jump)

    return True

Range Jump Template

def min_jumps(nums):
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

Heap Greedy Template

import heapq

def heap_greedy(items):
    heap = []

    for item in items:
        heapq.heappush(heap, transform(item))

    answer = []

    while heap:
        best = heapq.heappop(heap)
        process(best, answer)

    return answer

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Greedy algorithm 是一种每一步都做 local best decision，并且直接 commit 这个 decision 的算法。

它只在 local decision 可以被证明能导向 global optimum 时才正确。

核心性质是 greedy choice property：存在一个 optimal solution 包含 greedy choice。

常见证明方法是 exchange argument。如果某个 optimal solution 没有使用 greedy choice，我们尝试把它的一部分替换成 greedy choice。如果替换后答案不会变差，就说明 greedy choice 是 safe 的。

很多 greedy 问题从 sorting 开始。 Sorting key 非常关键。对 interval scheduling，按 end time 排序是因为最早结束的 interval 会给后续 intervals 留出最多空间。对 resource assignment，通常把 requirements 和 resources 都排序，用最小 sufficient resource 满足最小需求。

有些 greedy 问题基于 reachability。在 Jump Game 中，我维护 farthest reachable index。如果某个 index 超过 farthest，说明无法到达。在 Jump Game II 中，我把当前可达范围看成一层，当扫描到 current range 末尾时增加 jump count。

有些 greedy 问题需要全局 feasibility check。在 Gas Station 中，如果 total gas 小于 total cost，没有任何 start 可行。如果当前 tank 变成 negative，那么失败区间内所有 station 都不能作为 valid start。

有些 greedy 问题需要 heap。当 best available choice 会动态变化时， heap 可以高效取出当前最小或最大 candidate。这常见于 scheduling、frequency-based problems 和 resource allocation。

Greedy 最大的风险是没有证明就直接假设它正确。 Local optimum 不一定是 global optimum。如果无法解释为什么 greedy choice safe，我会考虑 DP 或 backtracking。

高级工程师解释 greedy 时，我会讲清楚： local greedy choice 是什么，为什么它 safe，维护什么 invariant，是否需要 sorting 或 heap， impossible case 如何检测，以及为什么 counterexample 不能破坏这个 strategy。

⭐ Final Insight

Greedy 的核心不是“每一步选看起来最好的”。

它的核心是证明这个 local choice 是 safe 的。

Senior-level 的重点是：

greedy choice 是什么，为什么这个选择不会破坏 future options，是否能用 exchange argument 证明， sorting key 为什么正确， invariant 是什么，以及什么时候 greedy 会失败、需要换成 DP。

能讲清楚这些， Greedy 就不是猜答案，而是一种基于 safe local decision 的优化策略。