</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

Scheduling and Greedy

What is this?

A receptionist allocating meeting rooms does two things at once. She works through requests in start-time order (a sort). And for each request she needs the room that frees up soonest, from a set that keeps changing (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.

Scheduling and greedy: sort by the constraint, let the heap manage the resource

Worked insight: 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, using 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.


In short: 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 valid; 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 a greedy should work (cut nearest the middle, or cut the cheapest piece first), and it does not: on a 7-unit stick with cuts at 2, 3 and 4, cutting 3 first costs 7 + 3 + 4 = 14, while cutting 4 first costs 7 + 4 + 2 = 13. 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 the standard way to model a pool of identical rooms or workers.
  • Worker pools and job queues. "Assign this job to the worker that frees up soonest" is the busy-heap pop.
  • Dispatch. Campus Bikes is a simple greedy version of matching nearby supply to demand with deterministic tie-breaks. Real dispatch systems usually optimise a global cost instead.
  • Capacity under a weakest-link rule. Maximum Performance of a Team is the pattern for "maximise a sum times a minimum": fix the minimum with a sort, then keep the best values in a heap.

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 + D) with distance bucketing (D = 1999 buckets), both with O(nm) space.

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(n) space (sorted pairs plus an O(k) heap).

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, O(n) space plus the sort.

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 (the bucket version gets this from generating pairs in worker-then-bike order).
  • Assuming greedy works on the stick. It does not (see the [2,3,4] example above). 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, so 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.

Maximum Performance of a Team

Core idea: Sort by descending efficiency so that the engineer you are standing on is the minimum efficiency of everyone considered so far. That fixes one factor of sum(speed) x min(efficiency), leaving a min-heap of the k fastest speeds to maximise the other.

Problem, rephrased

You're staffing a tiger team for a critical project from a bench of n engineers. You're given two arrays, speed, where speed[i] is how much work the i-th engineer ships per unit time, and efficiency, where efficiency[i] rates how cleanly that engineer works, plus an integer k, the headcount cap the budget allows. A team's performance is the sum of the speed of its members multiplied by the minimum efficiency among them: one sloppy member drags the whole team's quality bar down to theirs.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.