Scheduling and Greedy

What is this?

A receptionist allocating meeting rooms does two things at once. She works through requests in start-time order — that part is a sort. And for each request she needs the room that frees up soonest, from a set that keeps changing — that part is a heap. Neither tool alone solves it: sorting cannot track which rooms are occupied, and a heap has no idea which request to consider next.

Sort fixes the order of decisions. The heap fixes the choice at each decision. Almost every scheduling problem is that pairing.

💡 Fun fact: Maximum Performance of a Team is the cleanest example of why the sort order matters so much. Performance is sum(speeds) × min(efficiency), and the trap is that both factors pull in opposite directions. Sorting engineers by descending efficiency and walking the list fixes the minimum: when you are standing at engineer i, every engineer considered so far has efficiency at least e[i], so e[i] is the multiplier. All that remains is maximising the speed sum — a min-heap that evicts the slowest whenever the team exceeds k. The sort turns a two-variable optimisation into a one-variable one.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: sort by whatever fixes one of the two competing quantities, then use a heap to optimise the other. The sort is what makes the greedy provable; the heap is what makes it fast.

1. The two-heap room allocation

Meeting Rooms III needs both a heap of free rooms (ordered by room number, because ties go to the lowest) and a heap of busy rooms (ordered by when they free up):

free = list(range(n)); heapq.heapify(free)
busy = []                                  # (end_time, room)
for start, end in sorted(meetings):
    while busy and busy[0][0] <= start:    # release everything finished
        heapq.heappush(free, heapq.heappop(busy)[1])
    if free:
        room = heapq.heappop(free)
        heapq.heappush(busy, (end, room))
    else:                                   # all occupied → delay this meeting
        finish, room = heapq.heappop(busy)
        heapq.heappush(busy, (finish + (end - start), room))
    count[room] += 1

The while that releases finished rooms is what keeps the two heaps consistent, and the delayed-meeting branch is where implementations usually go wrong: the meeting keeps its duration, not its original end time, so the new end is finish + (end - start).

2. When greedy is wrong

Minimum Cost to Cut a Stick sits in this chapter as a deliberate counter-example. It feels like "always make the cheapest cut next", and that intuition is simply false — an early cheap cut can leave two expensive halves. The cost of a cut depends on the segment it sits in, which depends on every cut made before it, so the choices are not independent.

The correct approach is interval DP: add the two ends as sentinel cuts, sort, and compute the cheapest way to fully cut each interval by trying every cut inside it as the last one made.

dp[i][j] = min over k in (i, j) of  dp[i][k] + dp[k][j] + (cuts[j] - cuts[i])

Recognising that a greedy is unsafe is as valuable as knowing when it is safe — and interviewers put problems like this next to genuine greedies precisely to see whether you check.

3. Where you'll actually meet this

• Meeting room and resource booking. The two-heap allocation is what calendar systems actually run.
• Load balancers and worker pools. "Assign this job to the worker that frees up soonest" is the busy-heap pop.
• Kubernetes-style scheduling. Bin-packing pods onto nodes: sort by constraint, then pick the best-fit target from a changing set.
• Ride-hailing and delivery dispatch. Campus Bikes is literally the assignment problem for matching drivers to riders by distance with deterministic tie-breaks.
• CDN and cache placement. Choosing which items to keep under a budget, evicting the weakest, is the min-heap eviction from the team problem.

4. Problems in this chapter

▶ Campus Bikes

Assign each worker the closest available bike, breaking ties by worker index then bike index. Generate all pairs, sort by the composite key (or bucket by distance since it is bounded), and assign greedily while skipping taken pairs.
Pattern: sort by composite key + greedy assignment. Target: O(nm log(nm)), or O(nm) with distance bucketing.

▶ Maximum Performance of a Team

Maximise sum(speed) × min(efficiency) over at most k engineers. Sort by descending efficiency to fix the multiplier, then keep the k fastest with a min-heap.
Pattern: sort to fix one factor, heap to optimise the other. Target: O(n log n) time, O(k) space.

▶ Meeting Rooms III

Allocate n rooms to meetings, delaying when all are busy, and report the busiest room. Two heaps — free rooms by number, busy rooms by end time.
Pattern: dual-heap resource allocation. Target: O(m log m + m log n) time.

▶ Minimum Cost to Cut a Stick

Cut a stick at given positions, where each cut costs the length of the piece being cut. Not greedy — interval DP over the sorted cut positions with sentinels at both ends.
Pattern: interval DP. Target: O(m³) time, O(m²) space for m cuts.

5. Common pitfalls 🚫

• Sorting by the wrong key. In the team problem, ascending efficiency breaks the invariant entirely — the multiplier is only fixed when you walk descending.
• Recomputing the speed sum. Maintain it incrementally as engineers enter and leave the heap.
• Delaying a meeting to the wrong end time. It keeps its duration: finish + (end - start).
• One heap for rooms. Free and busy rooms are ordered by different keys and need separate heaps.
• Wrong tie-break in Campus Bikes. Distance, then worker index, then bike index — encode all three in the sort key rather than patching afterwards.
• Assuming greedy works on the stick. It does not. Try to construct a counter-example before committing to any greedy.
• Forgetting the sentinels in the interval DP — without both stick ends as cut positions, the segment lengths are wrong.

6. Key takeaways

1. Sort fixes the order; the heap fixes the choice. Most scheduling problems need exactly this pairing.
2. Sort to eliminate a variable. Descending efficiency turns a two-factor product into a one-factor maximisation.
3. Maintain running aggregates rather than recomputing them each iteration.
4. Two resources, two heaps, each ordered by its own key.
5. Check whether greedy is actually safe. If choices interact, it is not — reach for DP.
6. Encode tie-breaks in the sort key, never as a post-processing fix.
7. Why interviewers love it: these look like implementation problems and are really about justification. Why this sort order is the question behind the question.

Order: Campus Bikes → Maximum Performance of a Team → Meeting Rooms III → Minimum Cost to Cut a Stick.