Greedy with a Heap
What is this?
Both problems here have a greedy rule that is obvious in hindsight and needs a heap to execute. Attending the most events means, on each day, taking the one that expires soonest among those currently available. Spacing repeated characters means, at each position, emitting the one that is most frequent among those not on cooldown.
In each case the sort establishes when a decision is made, and the heap answers what to choose. Neither tool alone is enough.
Fun fact: Maximum Number of Events That Can Be Attended is a good example of a greedy whose obvious alternative is wrong. Taking the shortest event first seems natural and fails; taking the one with the earliest end date among those currently open is optimal, by the standard exchange argument. If an optimal schedule attends a later-ending event on some day, swapping in the earlier-ending one cannot hurt, because it frees at least as much future capacity. That is the same argument behind classic interval scheduling, applied one day at a time.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: advance a clock, admit everything now eligible, discard everything now impossible, then take the heap's top. The admit and expire steps before the choice are what make the greedy correct.
1. Admit, expire, choose
events.sort() # by start day
max_end = max(e for _, e in events)
heap, i, attended = [], 0, 0
for day in range(1, max_end + 1):
while i < len(events) and events[i][0] == day:
heapq.heappush(heap, events[i][1]); i += 1 # admit: now open
while heap and heap[0] < day:
heapq.heappop(heap) # expire: already too late
if heap:
heapq.heappop(heap); attended += 1 # choose: soonest deadline
return attended
The heap holds only end days. Admitting before choosing means an event that opens today can be today's pick. Expiring before choosing means you never attend something already past. Skipping either step gives a solution that is right on most inputs and wrong on the tight ones.
This day-by-day loop costs O(D + n log n), where D is the last day. That is fine when the horizon is small (day numbers up to about 10^5). When it is not, the lesson's main approach jumps instead of stepping: when the heap is empty, move straight to the next event's start day. Then each event is pushed once and popped once, and the cost is O(n log n) regardless of the day range.
2. Choose the most frequent, then cool it down
if k <= 1:
return s # no spacing required
heap = [(-count, ch) for ch, count in Counter(s).items()]
heapq.heapify(heap)
result, cooldown = [], deque() # (ready_at_index, count, ch)
while heap or cooldown:
if cooldown and cooldown[0][0] <= len(result):
_, cnt, ch = cooldown.popleft()
heapq.heappush(heap, (cnt, ch)) # its cooldown has elapsed
if not heap:
return "" # nothing legal to place: impossible
cnt, ch = heapq.heappop(heap)
result.append(ch)
if cnt + 1 < 0: # still has copies left
cooldown.append((len(result) + k - 1, cnt + 1, ch))
return "".join(result)
Taking the most frequent available character is what keeps the schedule feasible: the character with the most copies left is the one most likely to become impossible later, so it must be placed at the earliest legal opportunity. A character placed at slot t is barred for the next k - 1 slots and may return at slot t + k. Emptying the heap while the cooldown queue is still occupied is exactly the impossibility condition: no legal character exists for this position.
For example, s = "aaadbbcc" with k = 2 gives abacabcd, and s = "aaabc" with k = 3 gives "".
3. A 30-second worked example (events)
events = [[1,2], [2,3], [3,4], [1,2]]
All four events are attended. Note day 2: two events are open, and choosing the one ending today rather than the one ending tomorrow is what leaves day 3 free for the third event.
4. Where you'll actually meet this
- Conference and room scheduling. Maximising attended sessions under overlap is this exact greedy.
- Task queues with deadlines. Earliest-deadline-first is the classic real-time scheduling policy, and this is it with an admission step.
- Rate limiting and anti-spam. Spacing identical messages at least
kapart is the rearrangement problem under a different name. - Load spreading. Distributing repeated jobs across workers so the same job type is not run back to back.
- CPU task scheduling with cooldowns. The cooldown queue here is the same structure used for instruction scheduling.
5. Problems in this chapter
Maximum Number of Events That Can Be Attended
Attend as many events as possible, one event per day, on any day inside its window. Walk days forward, admit newly open events, expire the passed ones, then take the earliest deadline. The lesson compares jumping to the next start day with stepping through every day.
Pattern: admit, expire, attend with a min-heap of end days. Target: O(n log n) time and O(n) space with the jump; stepping through every day is O(D + n log n).
Rearrange String k Distance Apart
Rearrange so identical characters are at least k apart. Take the most frequent available character, then hold it on cooldown for k positions; an empty heap with a non-empty cooldown means it is impossible.
Pattern: frequency heap + cooldown queue. Target: O(n log a) for alphabet size a.
6. Common pitfalls
- Choosing the shortest event. It seems reasonable and is not optimal; earliest end date is.
- Choosing before admitting, which ignores events that open today.
- Choosing before expiring, which attends events already in the past.
- Solving a different problem. Here an event needs only one day inside its window. Treating each event as a block of days you must stay for is plain interval scheduling and gives smaller answers.
- Stepping through every day when day numbers can be huge. Jump to the next start day when the heap is empty.
- Taking the least frequent character in the rearrangement. The most frequent is the one at risk of becoming unplaceable.
- Returning the cooled character to the heap too early. A character placed at slot
tmay return at slott + k, so it is barred fork - 1slots. - Missing the impossible case. An empty heap with a non-empty cooldown queue means no valid arrangement exists.
- Mishandling small or large
k. Withk <= 1no spacing is needed, so returns. Withklarger than the string, only an all-distinct string works, and the general code returns""otherwise.
7. Key takeaways
- Admit, expire, then choose. Skipping either step before the choice breaks the greedy.
- Earliest deadline wins, and the exchange argument that proves it is one sentence.
- Most frequent first keeps a spacing schedule feasible, because that item is the one most likely to get stuck.
- A cooldown queue plus a heap models "eligible again after k steps" exactly.
- Detect impossibility explicitly. No legal choice is a real outcome, not an edge case.
- Jump to the next start day when the heap is empty rather than iterating every unit.
- Why interviewers like it: both greedies have plausible wrong alternatives, so the conversation goes straight to why yours is the right one.
Order: Maximum Number of Events That Can Be Attended → Rearrange String k Distance Apart.
Maximum Number of Events That Can Be Attended
Core idea: Walk the calendar one day at a time and, on each day, do three things in this order: admit every event that opens today into a min-heap keyed by end day, expire everything at the top that has already ended, then attend the one that ends soonest. Earliest-deadline-first is optimal by an exchange argument: if an optimal plan uses today for an event that closes later, swapping in the event that closes sooner never costs a future day. Admit and expire can swap places, because expiring only removes events that ended before today; both must happen before you attend, or you book an event that is already over or miss one that just opened. O(n log n).
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