Greedy ladder coding interview walkthrough

In this article

1. Before you start
2. Why interviewers ask this
3. Greedy scheduling from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the coding interview questions guide. "Greedy ladder" is this page's own name for the progression; it is not a standard textbook term.

Why interviewers ask this

A scheduling question with start and end times is a common wrapper for a greedy idea, and candidates report versions of it about ride-sharing drivers and cinema timetables. Interviewers use it to see whether you pick the sort key on purpose or by habit.

A weak answer says "sort the intervals and loop," without saying what to sort by. A strong answer names the key, states why it works, and notes the cost. A Staff-level answer also says how it could be wrong: it gives a counterexample for the tempting key, or a short exchange argument for the right one. The Kleinberg and Tardos slides by Kevin Wayne show that picking the ordering is the real work.

Greedy scheduling from first principles

Greedy algorithm

A greedy algorithm is a method that builds a solution step by step, at each step taking the choice that looks best by a fixed rule and never undoing it. Interval scheduling, Dijkstra's shortest paths, Huffman coding and Kruskal's spanning trees are all built this way.

Exchange argument

An exchange argument is a proof that swaps one item of an optimal solution for the greedy algorithm's choice and shows the result is no worse, so the greedy choice can always be made without loss.

Depth

The depth of a set of intervals is the largest number of them that contain any single moment in time, and it is the fewest rooms or workers that can serve them all.

In plain words

Picture a single meeting room and a pile of booking requests. You want to say yes to as many as possible. A greedy clerk sorts the requests by some rule, then walks down the pile and accepts a request whenever it does not clash with one already accepted. The analogy breaks in one place: a real clerk can change their mind, and a greedy algorithm never does. That is why the sort rule must be right from the start.

In one precise sentence, a greedy ladder is the same method, sort and then scan once, deciding each item for good, applied to three problems where only the sort key and the decision change: keep or skip, which room, or when it runs.

Step 1: Interval scheduling sorts by finish time

Interval scheduling asks for the largest set of jobs where no two overlap. The slides define job j as starting at sj and finishing at fj, and two jobs as compatible if they do not overlap. They list four natural orderings: earliest start time, earliest finish time, shortest interval and fewest conflicts. The first, third and fourth have counterexamples; earliest finish time is optimal.

Shortest interval fails on three rides, (0, 5), (4, 6) and (5, 10) (illustrative). The shortest, (4, 6), clashes with both others, so shortest-first keeps one ride, while earliest finish keeps (0, 5) and (5, 10), two rides.¹ The counterexample for fewest conflicts needs about a dozen intervals and is drawn in the slides.

Earliest start fails when one long job begins first and covers many short ones: greedy keeps the long job and loses all the short ones. So the rule is to sort by finish time, keep a job if its start is at least the last kept finish, and update that finish. The cost is O(n log n), dominated by the sort. You now know why the key matters; Step 2 changes the question.

Step 2: Interval partitioning sorts by start time and uses a heap

Interval partitioning asks for the fewest rooms so that no two lectures in one room overlap. The slides prove that the rooms needed are at least the depth, and the greedy rule meets that bound: consider lectures in increasing order of start time and assign each to any compatible room. The key flips to start time because processing lectures in start order makes the depth bound hold at each new room: a lecture that opens a new room finds that many lectures overlapping at its start, as the slides' proof shows.

To find a compatible room fast, the slides keep the rooms in a priority queue. In Python that is a min-heap of room finish times: if the smallest finish is no later than the new start, reuse that room, otherwise open a new one. The answer is the heap size at the end. The cost is O(n log n). This is the shape of the minimum-drivers question that candidates report, and of the widely searched "minimum meeting rooms" problem, which is the same question with meetings in place of rides. Assume a driver can start the next ride the moment the last one ends, with no travel time between locations.

Step 3: Scheduling with deadlines sorts by deadline

Scheduling to minimize lateness gives every job a processing time and a deadline, and all jobs must run, so the only decision is the order. The lateness of a job is how far past its deadline it finishes, or zero if it finishes on time; the slides write it as the larger of zero and finish minus deadline. The goal is to minimize the maximum lateness over all jobs.

Shortest processing time first and smallest slack both have counterexamples there. The right rule is earliest deadline first: run jobs back to back, with no idle time, in order of deadline. The key changed again, and so did the thing being minimized. Sorting by finish, start and deadline are three different tools, so copying the rung you remember is the mistake.

Step 4: Prove the key with an exchange argument or refute it

A greedy answer needs a proof or a counterexample, and interviewers listen for one. For interval scheduling, the proof takes an optimal solution that agrees with greedy for the longest possible prefix. If it differs next, replace its next job with greedy's next job, which finishes no later, so the swap stays compatible, the count is unchanged, and the prefix grows: a contradiction.

For lateness, the exchange claim is that swapping two consecutive inverted jobs reduces the number of inversions by one and does not raise the maximum lateness. To refute a rule instead, build the smallest input where it loses, as the long job above does.

1 · Finish time2 · Start time3 · Deadline4 · Prove itReplay

Step-by-step description

1. Interval scheduling keeps the most jobs.
2. Partitioning reuses rooms with a heap.
3. Earliest deadline first minimizes lateness.
4. Use an exchange argument or a counterexample.

• Rung one sorts by finish time to keep the most jobs.
• Rung two sorts by start time and reuses rooms with a heap.
• Rung three sorts by deadline to minimize maximum lateness.
• An exchange argument or counterexample checks each rung.

Rung one sorts by finish time to keep the most jobs, rung two sorts by start time and reuses rooms with a heap, rung three sorts by deadline to minimize maximum lateness, and an exchange argument or counterexample checks each rung.

Worked example

Take six rides, each as a start and end time, treating an end as free for a ride that starts at that same time (illustrative): A (1, 4), B (2, 3), C (3, 5), D (4, 7), E (5, 8) and F (6, 9).¹

Sorted by finish time, greedy keeps B, then C, then E, which is three rides; A, D and F are skipped for overlapping the last kept ride. Sorted by earliest start instead, it keeps A, then D, only two rides, so earliest start loses.¹ On a second illustrative set, one long ride from 0 to 10 and three short ones inside it, earliest start keeps one ride and earliest finish keeps three.¹

For rooms, process the rides in start order with a heap of room end times:

The overlap peaks at three rides at time six, so the depth is three and the heap size agrees, as the slides' depth bound says.¹

Text description of the diagram

• The overlap peaks at three rides at time six.
• The depth is three and the heap size agrees.

Here is the code for the two ride problems, in Python. Both functions were run on the six rides, each ride a (start, end) pair, and return 3 and 3.¹

import heapq

def max_non_overlapping(rides):
    """Interval scheduling: sort by finish time, keep what fits."""
    last_end = float("-inf")
    kept = 0
    for start, end in sorted(rides, key=lambda r: (r[1], r[0])):
        if start >= last_end:      # touching ends are allowed
            kept += 1
            last_end = end
    return kept

def min_drivers(rides):
    """Interval partitioning: sort by start, heap of end times."""
    heap = []
    for start, end in sorted(rides):
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)   # reuse the free driver
        else:
            heapq.heappush(heap, end)      # open a new driver
    return len(heap)

The first function sorts by finish time and keeps a ride whenever its start is at least the last kept end. The second sorts by start time and keeps one heap entry per driver; heapreplace pops the earliest end and pushes the new one in a single step, and the heap size is the answer.

For lateness, use six jobs in the style of the slides' example, as (time, deadline) and illustrative: (3, 6), (2, 8), (1, 9), (4, 9), (3, 14) and (2, 15). Earliest deadline first finishes at times 3, 5, 6, 10, 13 and 15, so only the fourth job is late, by 1. Shortest processing time first runs the jobs in a different order and reaches a maximum lateness of 6.¹ For scale, n times log₂ n for a million rides is about 20 million, a ballpark and not an exact comparison count; the minimum any comparison sort needs is log₂(n!), about 18.5 million.¹

Trade-offs and edge cases

Greedy is fast but correct only when the key fits the problem. The first rung fails with three natural keys, as the figure below shows: earliest start, shortest interval and fewest conflicts fail on interval scheduling, while earliest finish is optimal.

Text description of the diagram

• Earliest start, shortest interval and fewest conflicts fail on interval scheduling.
• Earliest finish is optimal.

Edge cases to settle aloud. First, ties and touching ends: decide whether a job that starts exactly when another ends is compatible, as the worked example does, and keep the comparison consistent (>= or >). Second, the cost is O(n log n), not O(n), because the sort dominates the scan. Third, the loop never reconsiders a choice, so problems where one choice changes the cost of others are not greedy. Candidates report an assignment of food orders to drivers by location; with one order per driver and travel time as the cost, that is a minimum-cost matching, called the assignment problem, and the follow-up below shows why nearest-first fails.

Candidates also report scheduling tasks for maximum profit with deadlines; the usual greedy for unit-time tasks sorts by reward and places each in the latest free slot before its deadline. A reported cinema question asks whether a new movie fits a sorted schedule inside opening hours: compare it with its neighbours and the opening and closing times. A fixed-budget throughput question reads like a knapsack, so ask whether items can be split before choosing.

Related patterns: merge intervals uses the same sort-and-sweep shape, and longest substring without repeating characters is a different kind of one-pass method.

How to answer it in an interview

The spoken structure: name the sort key, say the data structure, give the cost, then give the one-line proof.

Common mistakes

• "I'll sort by shortest ride." (wrong) A short ride can overlap the end of one long ride and the start of another, blocking both. (right) "I sort by finish time, because that leaves the most room for later jobs."
• "Greedy is O(n)." (wrong) The scan is linear but the sort is not. (right) "The sort dominates, so it is O(n log n)."
• "The rooms needed are the number of overlapping pairs." (wrong) Pairs overcount. (right) "The rooms needed equal the depth, the most rides at one time."
• "The same key works for all scheduling problems." (wrong) The three rungs use finish, start and deadline. (right) "I choose the key from what the problem minimizes or maximizes."
• "It passed my examples, so it is correct." (wrong) A plausible key can pass many tests. (right) "I will give an exchange argument or a smallest counterexample."

Follow-up questions

How do you find the minimum number of drivers needed to serve a list of rides?

Sort by start time, keep a min-heap of end times, and reuse the driver with the earliest end when it is free. The final heap size is the answer and equals the peak overlap; the same problem is searched as "minimum meeting rooms". Python's undefined provides heappush and heappop for this.

Can greedy assign food orders to drivers to minimize total delivery time?

Not with nearest-pair-first. With one order per driver and travel time as the cost, the problem is a minimum-cost bipartite matching, called the assignment problem, which the Hungarian algorithm solves in polynomial time; min-cost flow covers drivers who can take several orders. Take two drivers and two orders with illustrative distances 1 and 2 for the first driver and 2 and 10 for the second: the nearest pair (1) leaves the other driver the order at distance 10, a total of 11, while swapping the pairs costs 4.¹

How do you maximize throughput under a fixed budget?

Ask what each process costs and gains, and whether an item can be split. If it can, sorting by gain per cost is the usual greedy; if each item is all or nothing, it is usually a knapsack problem and needs dynamic programming.

How do you know a greedy choice is correct?

Give an exchange argument: swap one item of an optimal solution for the greedy choice and show nothing gets worse. If you cannot, look for a small counterexample.

What if two jobs finish at the same time?

Break the tie consistently, for example by earlier start; Python's sort is stable, so equal keys keep their input order, as the Python documentation on sorting techniques explains. For interval scheduling of intervals with positive length either choice keeps the count correct, but the rule must be stated.

For ordering items in a graph rather than sorting a list, see topological sort, and for language details see Python interview questions.

Sources

1. Chapter 4 Greedy Algorithms (slides by Kevin Wayne for Kleinberg and Tardos, Algorithm Design) — Princeton University Computer Science / Pearson (accessed 2026-10-26), 1 Jan 2005
2. heapq: Heap queue algorithm — Python Software Foundation (accessed 2026-10-26), 26 Oct 2026
3. Sorting Techniques (Python HOWTO) — Python Software Foundation (accessed 2026-10-26), 26 Oct 2026