readyforhires
Sign up free

Greedy & Intervals 101

Intermediate · 4 chapters · 8 min read · Make the locally best choice, and learn how to prove it is also globally best.

Practise this in the app All guides

What greedy means

Commit and never look back

A greedy algorithm builds the answer one step at a time, always taking the choice that looks best right now, and never undoing it. When it works, it is usually the shortest and fastest solution: often a sort followed by one pass. When it does not work, it gives confidently wrong answers, which is why interviewers care as much about why your greedy choice is safe as about the code.

Signals in a problem statement

Greedy versus dynamic programming

Both make a sequence of decisions. Greedy commits to one choice per step; DP tries every choice and remembers the best. If you can find a small counter-example where the obvious greedy choice fails (coins [1, 3, 4] making 6: greedy takes 4 + 1 + 1, but 3 + 3 is better), switch to DP.

How to justify a greedy choice

Use the exchange argument: take any optimal solution that differs from yours at the first step, swap in your greedy choice, and show the result is no worse. For interval scheduling: among all meetings, the one that ends earliest leaves the most room for the rest, so an optimal schedule can always be rearranged to start with it. One or two sentences like this are enough in an interview, and they show you are not just guessing.

Core patterns with templates

1. Sort by end, keep what fits

The maximum number of non-overlapping intervals; the number to remove is n - kept.

def erase_overlap(intervals):
    intervals.sort(key=lambda x: x[1])
    kept, end = 0, float("-inf")
    for s, e in intervals:
        if s >= end:
            kept += 1
            end = e
    return len(intervals) - kept

Shooting balloons with arrows is the same idea: one arrow at the end of the earliest-ending balloon bursts every balloon that starts at or before it.

2. Merge overlapping intervals (sort by start)

def merge(intervals):
    intervals.sort()
    out = []
    for s, e in intervals:
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

3. Farthest reach

def can_jump(nums):
    reach = 0
    for i, x in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + x)
    return True

Example: [3, 2, 1, 0, 4] gets stuck at index 4 because the reach never passes 3.

4. Match smallest with smallest

def content_children(greed, cookies):
    greed.sort()
    cookies.sort()
    i = 0
    for c in cookies:
        if i < len(greed) and c >= greed[i]:
            i += 1
    return i

5. Two passes for neighbour constraints

def candy(ratings):
    n = len(ratings)
    c = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            c[i] = c[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            c[i] = max(c[i], c[i + 1] + 1)
    return sum(c)

The left pass satisfies left neighbours, the right pass satisfies right neighbours, and max keeps both.

Complexity, mistakes and edge cases

Complexity

Most greedy solutions are O(n log n) because of the initial sort, followed by an O(n) scan. Those without sorting (jump game, candy) are O(n). Extra space is usually O(1) beyond the sort, or O(n) for an auxiliary array like the candy counts.

Common mistakes

Edge cases

An empty list of intervals, a single interval, intervals that are all identical, intervals nested inside each other, negative coordinates, [0] for jump game (already at the end), and ratings that are all equal (everyone gets one candy).

Checking a greedy quickly

Write a tiny brute force (try every subset) for inputs of size four or five, and compare it with your greedy on a few random cases. You will not do this in a live interview, but doing it during practice builds the intuition for which greedy choices are safe.

Variations and practise

How interviewers twist it

How to explain it

Say the rule and the reason together: "I sort by end time and take each interval that starts after the last one I kept, because finishing earliest leaves the most room." That sentence covers both the code and the proof.

Practise

The problems below cover reachability with jumps, matching smallest to smallest, two-pass neighbour constraints, and the two classic interval problems (removing overlaps and bursting balloons). For each, write the sort key and the comparison (> or >=) before you write the loop.

Practise

Easy

Medium

Hard

Practise this in the app All guides