Priority Queue Greedy
Dynamic Selection with Priority Queues
Here's something that takes a while to click: some greedy problems can't be solved by sorting alone because the set of available choices changes over time. You sort jobs by deadline, but new jobs become eligible as you move through time. You sort guests by arrival, but rooms free up as earlier guests leave.
The priority queue bridges this gap. It lets you always pick the best option currently available, updating the pool as the world changes around you.
This lesson covers six problems. The first three — Summer Vacation, Room Allocation, and Packing Under Range Regulations — deserve the deepest treatment. They represent three distinct PQ patterns that appear over and over in competitive programming.
Example 1: ABC137D — Summer Vacation
Problem. \(n\) jobs, each with reward \(a_i\) and deadline \(b_i\) (the job takes \(b_i\) days to complete, so it must be started at least \(b_i\) days before the end). You can do one job per day over \(m\) days. Maximize total reward.
The Greedy Choice: On each day, pick the highest-reward job from the pool of currently available jobs. The priority queue always surfaces the best option.
The Wrong Approach
Your first instinct: "Sort jobs by reward descending, greedily pick the best ones." But a high-reward job might have a tight deadline that conflicts with another high-reward job. Pure reward sorting ignores timing.
Your second instinct: "Sort by deadline, earliest first." But that wastes high-value jobs on slots that could go to even better jobs arriving later.
Instead of asking "which jobs should I do first?", ask: "as time passes, which new jobs become doable, and which available job is best right now?"
The Mental Model: Iterate Days Left
The cleanest way to think about this: iterate daysLeft from 1 to \(m\). On the step where daysLeft = d, any job with deadline \(d\) becomes available — it takes exactly \(d\) days, and we now have enough days remaining to complete it. Push these jobs into a max-heap, then pop the highest reward.
This forward scan is equivalent to the reverse-time approach but has a simpler mental model: as we gain more time budget, more jobs unlock.
Step-by-Step Trace
Stare at this table. \(n = 5\) jobs, \(m = 4\) days.
| Job | Reward | Deadline (\(b_i\)) |
|---|---|---|
| A | 3 | 4 |
| B | 7 | 2 |
| C | 1 | 1 |
| D | 5 | 3 |
| E | 4 | 1 |
Processing by daysLeft from 1 to 4:
| daysLeft | New jobs unlocked (deadline = daysLeft) | PQ contents | Pick | Running total |
|---|---|---|---|---|
| 1 | C (b=1, r=1), E (b=1, r=4) | {4, 1} | 4 (E) | 4 |
| 2 | B (b=2, r=7) | {7, 1} | 7 (B) | 11 |
| 3 | D (b=3, r=5) | {5, 1} | 5 (D) | 16 |
| 4 | A (b=4, r=3) | {3, 1} | 3 (A) | 19 |
Total reward = 19. We used all 4 days, skipped job C (reward 1).
Verify: Could we do better? The maximum possible is the sum of the top 4 rewards: \(7 + 5 + 4 + 3 = 19\). And all 4 fit within their deadlines. Optimal.
The Code
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int numJobs, numDays;
cin >> numJobs >> numDays;
vector<vector<int>> jobsByDeadline(numDays + 1);
for (int i = 0; i < numJobs; i++) {
int reward, deadline;
cin >> reward >> deadline;
if (deadline <= numDays) {
jobsByDeadline[deadline].push_back(reward);
}
}
priority_queue<int> availableRewards;
long long maxTotalReward = 0;
for (int daysLeft = 1; daysLeft <= numDays; daysLeft++) {
for (int reward : jobsByDeadline[daysLeft]) {
availableRewards.push(reward);
}
if (!availableRewards.empty()) {
maxTotalReward += availableRewards.top();
availableRewards.pop();
}
}
cout << maxTotalReward << "\n";
return 0;
}
\(O(n \log n)\) time — each job is pushed and popped at most once.
Example 2: CSES — Room Allocation
Problem. \(n\) guests arrive on day \(a_i\) and leave on day \(b_i\). Assign each guest a room. Minimize rooms used. Two guests can share a room if their stays don't overlap (guest 1 leaves on day \(b_1\) before guest 2 arrives on day \(a_2\), where \(a_2 > b_1\)).
The Wrong Approach
You might try: "Sort by duration, assign short stays first." But duration is irrelevant — what matters is when stays overlap.
Instead of asking "which guests are easy to assign?", ask: "when a new guest arrives, is there a room that just freed up?"
The Greedy with a Min-Heap
Sort guests by arrival time. Maintain a min-heap of (departure_day, room_number). The top of the heap is the room that frees up earliest.
For each guest: 1. Check if the earliest-freeing room has departure < current arrival (room is free) 2. If yes, reuse that room: pop it, push (new_departure, same_room) 3. If no, allocate a new room: push (new_departure, new_room)
Step-by-Step Trace
Stare at this table. 5 guests:
| Guest | Arrival | Departure |
|---|---|---|
| G1 | 1 | 3 |
| G2 | 2 | 5 |
| G3 | 4 | 6 |
| G4 | 4 | 7 |
| G5 | 6 | 8 |
Sorted by arrival (already sorted):
| Step | Guest | Min-heap top | Room freed? | Action | Heap after |
|---|---|---|---|---|---|
| 1 | G1 (1-3) | empty | — | New room 1 | {(3,R1)} |
| 2 | G2 (2-5) | (3,R1) | \(3 < 2\)? No | New room 2 | {(3,R1), (5,R2)} |
| 3 | G3 (4-6) | (3,R1) | \(3 < 4\)? Yes | Reuse R1 | {(5,R2), (6,R1)} |
| 4 | G4 (4-7) | (5,R2) | \(5 < 4\)? No | New room 3 | {(5,R2), (6,R1), (7,R3)} |
| 5 | G5 (6-8) | (5,R2) | \(5 < 6\)? Yes | Reuse R2 | {(6,R1), (7,R3), (8,R2)} |
Result: 3 rooms. This equals the maximum number of overlapping intervals at any point (guests G2, G3, G4 all overlap on days 4-5).
Manual verification: On day 4, G2 (2-5), G3 (4-6), and G4 (4-7) are all present. You need at least 3 rooms. We used exactly 3. Optimal.
The Code
auto arrivalCompare = [](const array<int, 3>& guest1, const array<int, 3>& guest2) {
return guest1[0] < guest2[0];
};
sort(guests.begin(), guests.end(), arrivalCompare);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> activeRooms;
int totalRooms = 0;
vector<int> roomAssignment(numGuests);
for (int i = 0; i < numGuests; i++) {
if (!activeRooms.empty() && activeRooms.top().first < guests[i][0]) {
int freedRoom = activeRooms.top().second;
activeRooms.pop();
roomAssignment[guests[i][2]] = freedRoom;
activeRooms.push({guests[i][1], freedRoom});
} else {
totalRooms++;
roomAssignment[guests[i][2]] = totalRooms;
activeRooms.push({guests[i][1], totalRooms});
}
}
Example 3: ABC214E — Packing Under Range Regulations
Problem. \(10^9\) boxes (positions on a number line), \(N\) balls. Ball \(i\) must be placed in a box numbered in \([L_i, R_i]\). Each box holds at most 1 ball. Can all balls be placed?
The Structural Insight: Earliest Deadline First
This is the Earliest Deadline First (EDF) pattern applied to interval assignment. Instead of asking "which ball goes where?", ask: "at each position, which available ball is most urgent to place?"
The most urgent ball is the one with the smallest \(R_i\) — its deadline is tightest. If you don't place it soon, you'll miss its window entirely.
The Algorithm
- Sort balls by \(L_i\) (left endpoint).
- Sweep positions left to right. At each position:
- Add all balls whose \(L_i \leq\) current position to a min-heap (keyed on \(R_i\))
- If the heap's top has \(R_i <\) current position, a ball's deadline has passed. Impossible.
- Otherwise, pop the top (most urgent ball) and assign it to this position.
Step-by-Step Trace
5 balls:
| Ball | \(L\) | \(R\) |
|---|---|---|
| A | 1 | 3 |
| B | 1 | 2 |
| C | 2 | 4 |
| D | 3 | 5 |
| E | 3 | 3 |
Sorted by \(L\): B(1,2), A(1,3), C(2,4), E(3,3), D(3,5).
| Pos | Balls added | Min-heap (by \(R\)) | Top \(R <\) pos? | Assign | Heap after |
|---|---|---|---|---|---|
| 1 | B(R=2), A(R=3) | {2, 3} | \(2 < 1\)? No | B (\(R=2\)) | {3} |
| 2 | C(R=4) | {3, 4} | \(3 < 2\)? No | A (\(R=3\)) | {4} |
| 3 | E(R=3), D(R=5) | {3, 4, 5} | \(3 < 3\)? No | E (\(R=3\)) | {4, 5} |
| 4 | — | {4, 5} | \(4 < 4\)? No | C (\(R=4\)) | {5} |
| 5 | — | {5} | \(5 < 5\)? No | D (\(R=5\)) | {} |
All 5 balls placed. Yes.
What breaks if you use a max-heap instead? At position 1, you'd assign A (\(R=3\)) — the least urgent ball. B (\(R=2\)) stays in the heap. At position 2, you'd assign C (\(R=4\)). Now B is still unassigned with \(R=2\), and position 2 was its last chance. At position 3, the heap has {2, 3, 5}. Top \(= 2 < 3\). B's deadline passed. Failure. Always pick the most urgent, not the least.
The Code
auto leftEndpointCompare = [](const pair<int, int>& ball1, const pair<int, int>& ball2) {
return ball1.first < ball2.first;
};
sort(balls.begin(), balls.end(), leftEndpointCompare);
priority_queue<int, vector<int>, greater<int>> deadlineHeap;
int ballIndex = 0;
for (int currentPosition = 1; currentPosition <= maxPosition; currentPosition++) {
while (ballIndex < numBalls && balls[ballIndex].first <= currentPosition) {
deadlineHeap.push(balls[ballIndex].second);
ballIndex++;
}
if (!deadlineHeap.empty() && deadlineHeap.top() < currentPosition) {
cout << "No\n";
return;
}
if (!deadlineHeap.empty()) {
deadlineHeap.pop();
}
}
cout << (deadlineHeap.empty() ? "Yes" : "No") << "\n";
Important detail: With \(10^9\) possible positions but only \(N\) balls, you don't iterate all positions. Instead, use coordinate compression — only visit positions where something changes (ball starts or you need to place).
Example 4: ABC195D — Shipping Center
Problem. \(N\) items (size \(W_i\), value \(V_i\)), \(M\) boxes (capacity \(X_i\)). Each box holds 1 item. \(Q\) queries: given a subset of available boxes, maximize total value.
The Greedy: Most Valuable First, Tightest Fit
Sort items by value descending. For each item (most valuable first), assign it to the smallest box that fits — this leaves larger boxes free for bigger items.
Why tightest fit? If you assign a small item to a huge box, you "waste" capacity. A later, larger, less-valuable item might have needed that box. By always using the smallest sufficient box, you maximize the remaining capacity for future assignments.
Trace
Items: (\(W=3, V=10\)), (\(W=5, V=8\)), (\(W=2, V=6\)). Boxes: [4, 6, 3].
Sorted by value: (3,10), (5,8), (2,6).
| Item | \(W\) | \(V\) | Available boxes | Smallest fit | Assign? |
|---|---|---|---|---|---|
| 1 | 3 | 10 | {3, 4, 6} | 3 | Yes, box 3 |
| 2 | 5 | 8 | {4, 6} | 6 | Yes, box 6 |
| 3 | 2 | 6 | {4} | 4 | Yes, box 4 |
Total value \(= 10 + 8 + 6 =\) 24. All items fit.
What would happen if we assigned item 1 to box 6 instead? Remaining boxes {3, 4}. Item 2 (\(W=5\)) doesn't fit in 3 or 4. We lose value 8. Tightest fit prevents this.
The Code
auto valueCompareDescending = [](const pair<int, int>& item1, const pair<int, int>& item2) {
return item1.second > item2.second;
};
sort(items.begin(), items.end(), valueCompareDescending);
for (const auto& item : items) {
auto bestBoxIt = availableBoxes.lower_bound(item.first);
if (bestBoxIt != availableBoxes.end()) {
totalValue += item.second;
availableBoxes.erase(bestBoxIt);
}
}
Exchange argument: If we assigned a valuable item to a large box and a less valuable item to a tight-fitting box, swapping assignments (if the valuable item fits in the smaller box) never worsens the result.
Example 5: ABC080D — Recording
Problem. Record \(N\) TV programs. Program \(i\) airs on channel \(c_i\) from time \(s_i\) to \(t_i\). A recorder can record consecutive programs on the same channel, but switching channels requires a gap. Minimize recorders.
Key insight: Two programs can share a recorder if: - Same channel AND the second starts right when the first ends (no gap needed) - Different channels AND there's a gap between them
Solution: Model as interval scheduling with channel constraints. Sort by start time. Use a PQ of (end_time, channel, recorder_id). For each program, try to reuse a recorder — prefer one that finished on the same channel (no gap needed), otherwise one that finished early enough on a different channel. If neither works, allocate a new recorder.
Challenge: Why does preferring "same channel, latest finish" over "different channel, earliest finish" give the optimal result? Think about what resource you're conserving.
Example 6: UVa 11264 — Coin Collector
Problem. Given coin denominations where change is given using the greedy algorithm (largest denomination first), you make a purchase and want to maximize the number of distinct coins in your change.
Structural insight: In a canonical coin system, the greedy change algorithm uses specific denominations. To maximize distinct coins, choose a payment amount that forces the greedy change algorithm to use as many different denominations as possible.
Solution: Greedily accumulate denominations from smallest to largest: include denomination \(d_i\) if the running sum stays below \(d_{i+1}\).
Try it yourself: Given denominations \([1, 5, 10, 25, 50]\), what running sum do you build? Start: 1. Add 5: sum \(= 6 < 10\), include. Add 10: sum \(= 16 < 25\), include. Add 25: sum \(= 41 < 50\), include. Add 50: sum \(= 91\), no larger denomination to check. Include. Answer: 5 distinct coins.
When to Use PQ Greedy
Here's a summary of the patterns you've seen:
- "Best available" selection (Summer Vacation): Options become available over time, always pick the best current option. Use a max-heap.
- Resource reuse (Room Allocation): When finished resources become available again. Sort by start, min-heap on end times.
- Earliest Deadline First (Packing Under Range): Assign the most urgent item first. Sort by start, min-heap on deadlines.
- Tightest fit assignment (Shipping Center): Match items to resources with minimal waste. Use a multiset/ordered set with
lower_bound. - Event-driven processing (Recording): Sort events by time, maintain state in a heap, handle transitions.
- Merge-based construction (Huffman Coding): Repeatedly merge the two smallest elements. Covered in depth in Chapter 8 Lesson 3.
Instead of asking "should I sort by start or end or value?", ask: "what changes over time, and at each moment, what's the best choice from the current pool?" If the pool changes dynamically, you need a priority queue.
Try It
Warm-up 1: Summer Vacation by Hand
3 jobs, 3 days:
| Job | Reward | Deadline |
|---|---|---|
| A | 10 | 1 |
| B | 5 | 2 |
| C | 8 | 1 |
Predict before tracing: What's the maximum reward? Which job gets skipped?
Trace the forward processing:
- daysLeft = 1: unlock A(10) and C(8) (deadline 1). PQ = {10, 8}. Pick 10 (A). Total = 10.
- daysLeft = 2: unlock B(5) (deadline 2). PQ = {8, 5}. Pick 8 (C). Total = 18.
- daysLeft = 3: no new jobs. PQ = {5}. Pick 5 (B). Total = 23.
All 3 jobs fit. Total = 23. No job gets skipped.
Warm-up 2: Room Allocation Edge Case
3 guests, all arriving on the same day:
| Guest | Arrival | Departure |
|---|---|---|
| G1 | 1 | 5 |
| G2 | 1 | 3 |
| G3 | 1 | 4 |
How many rooms? Trace the algorithm. Predict first.
Since all arrive on day 1 and no room has freed up before any arrival, you need 3 rooms. The min-heap never has a departure < arrival for any guest.
Challenge: EDF Failure Mode
Consider these balls: A(1,2), B(1,2), C(1,2), with only 2 box positions available (positions 1 and 2). Can all 3 balls be placed? How does the algorithm detect failure?
At position 1: add all 3 balls. PQ = {2, 2, 2}. Assign one. PQ = {2, 2}. At position 2: PQ top = 2. Is \(2 < 2\)? No. Assign one. PQ = {2}. No more positions. PQ is not empty (1 ball remains). Output: No.
The algorithm detects failure when the heap isn't empty after processing all positions.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| ABC137D — Summer Vacation | atcoder.jp/contests/abc137/tasks/abc137_d | 400pts |
| CSES — Room Allocation | cses.fi/problemset/task/1164 | Medium |
| ABC214E — Packing Under Range Regulations | atcoder.jp/contests/abc214/tasks/abc214_e | 500pts |
| ABC195D — Shipping Center | atcoder.jp/contests/abc195/tasks/abc195_d | 400pts |
| ABC080D — Recording | atcoder.jp/contests/abc080/tasks/abc080_d | 400pts |
| UVa 11264 — Coin Collector | onlinejudge.org | Medium |
| LC 1094 — Car Pooling | leetcode.com/problems/car-pooling | Medium |
| LC 621 — Task Scheduler | leetcode.com/problems/task-scheduler | Medium |
| LC 767 — Reorganize String | leetcode.com/problems/reorganize-string | Medium |