Advanced Greedy Interview Patterns: Interval Scheduling, Jump Game, and Huffman Coding (2025)

By /
⏱ 6 min read

When Does Greedy Work?

Greedy works when the locally optimal choice at each step leads to a globally optimal solution. Formal condition: the problem has the “greedy choice property” — making the locally optimal choice never eliminates a globally optimal solution. Proof technique: exchange argument. Assume the greedy solution is not optimal. Show that any optimal solution can be transformed, step by step, into the greedy solution without worsening the result. This contradiction proves the greedy is optimal. Greedy vs DP: if the greedy choice property holds, greedy is faster and simpler than DP. If it doesn’t hold (the locally optimal choice can prevent reaching the global optimum), use DP. Litmus test: can you prove that the greedy choice is always safe? If you can’t, it might be DP.

Pattern 1: Interval Scheduling

Non-overlapping intervals (LC 435 Minimum Number of Intervals to Remove, LC 452 Minimum Arrows for Balloons): sort by end time. Greedy: always select the interval ending earliest — this leaves the maximum room for future intervals. For LC 435: count non-overlapping intervals by greedily selecting the earliest-ending ones. Intervals to remove = total – count. For LC 452 (balloons): count the minimum number of arrows. Sort by end. One arrow at the end of the first interval pops all overlapping balloons. Move to the first non-overlapping balloon and repeat.

def min_arrows(points):
    points.sort(key=lambda x: x[1])  # sort by end
    arrows = 1
    end = points[0][1]
    for start, finish in points[1:]:
        if start > end:  # new non-overlapping group
            arrows += 1
            end = finish
    return arrows

Pattern 2: Jump Game (LC 55, 45)

LC 55 (can reach end?): track max_reach. At each position i, if i > max_reach: stuck. Otherwise: max_reach = max(max_reach, i + nums[i]). If max_reach >= n-1: return True. LC 45 (minimum jumps): greedy BFS-style. Track current_end (farthest reach of current jump) and farthest (farthest reach of next jump). When i reaches current_end: increment jumps, set current_end = farthest. This is O(n) vs O(n^2) DP.

def jump(nums):
    jumps = 0
    current_end = 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

Pattern 3: Task Scheduler (LC 621)

Given tasks with frequencies and a cooldown n between same-task types: find minimum time to complete all tasks. Greedy: always run the most frequent remaining task. Formula: compute max_count = most frequent task’s count. max_count_tasks = number of tasks with that frequency. Result = max((max_count – 1) * (n + 1) + max_count_tasks, total_tasks). Intuition: arrange the most frequent task in “blocks” of (n+1): [A, _, _, A, _, _, A]. Fill blanks with other tasks. If there are enough tasks to fill all blanks: no idle time needed; result = total_tasks. Otherwise: idle time = (max_count – 1) * (n + 1) + max_count_tasks – total_non_max_tasks.

Pattern 4: Huffman Coding / Greedy on Heap

Build an optimal prefix-free encoding: merge the two least-frequent symbols repeatedly. Use a min-heap. Extract two minimums, combine (sum their frequencies), re-insert. Repeat until one node remains. This is a greedy algorithm: merging the two smallest at each step is provably optimal (exchange argument: swapping the smallest pair with any other pair would not decrease the total encoding cost). O(n log n) time. Pattern generalizes: whenever you need to greedily combine the two smallest values, a min-heap is the right data structure. LC 1167 (Minimum Cost to Connect Sticks): same algorithm — merge the two shortest sticks, pay the combined length as the cost. LC 502 (IPO): two-heap problem — one min-heap for capital requirements, one max-heap for profits. Greedily take the highest-profit project you can currently afford.

Pattern 5: Candy / Allocation Problems

LC 135 (Candy): each child gets at least 1 candy; children with higher ratings than neighbors get more. Two-pass greedy: left-to-right pass enforces the “higher than left neighbor” rule. Right-to-left pass enforces the “higher than right neighbor” rule. Take the max of both passes. Two passes is a common pattern for problems with constraints from both directions.

Asked at: Meta Interview Guide

Asked at: Apple Interview Guide

Asked at: Coinbase Interview Guide

Asked at: Atlassian Interview Guide

Scroll to Top