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 — and 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.

The one-line idea: advance a clock, admit everything now eligible, discard everything now impossible, then take the heap's top. The admit-and-expire step before the choice is what makes the greedy correct.

1. Admit, expire, choose

events.sort()                                    # by start day
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 order of the three steps is the algorithm. Admitting before expiring means an event that opens and closes on the same day is still considered. Expiring before choosing means you never attend something already past. Getting these backwards produces a solution that is right on most inputs and wrong on the tight ones.

Iterating day by day is fine when the horizon is bounded; when it is not, jump to the next interesting day — the smaller of the next start and the current heap top.

2. Choose the most frequent, then cool it down

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. Emptying the heap while the cooldown queue is still occupied is exactly the impossibility condition — no legal character exists for this position.

3. A 30-second worked example (events)

events = [[1,2], [2,3], [3,4], [1,2]]

day 1:  admit [1,2] and [1,2]        heap ends = [2, 2]
        expire: none (2 >= 1)
        attend the one ending day 2  → heap = [2]            attended = 1

day 2:  admit [2,3]                  heap = [2, 3]
        expire: none (2 >= 2)
        attend the one ending day 2  → heap = [3]            attended = 2

day 3:  admit [3,4]                  heap = [3, 4]
        expire: none
        attend the one ending day 3  → heap = [4]            attended = 3

day 4:  attend the one ending day 4                          attended = 4

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 k apart 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 per day. Walk days forward, admit newly-open events, expire the passed ones, then take the earliest deadline.
Pattern: admit–expire–choose with a min-heap. Target: O(n log n) time, O(n) space.

▶ 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.
• Expiring before admitting, which drops events that open and close on the same day.
• Choosing before expiring, which attends events already in the past.
• 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. It becomes eligible after k positions, not k − 1.
• Missing the impossible case. An empty heap with a non-empty cooldown queue means no valid arrangement exists.
• Treating k <= 1 as a special case — it needs no spacing at all, and the general code should handle it, but check.

7. Key takeaways

1. Admit, expire, then choose. The order of those three steps is the correctness argument.
2. Earliest deadline wins, and the exchange argument that proves it is one sentence.
3. Most frequent first keeps a spacing schedule feasible, because that item is the one most likely to become stuck.
4. A cooldown queue plus a heap models "eligible again after k steps" exactly.
5. Detect impossibility explicitly — no legal choice is a real outcome, not an edge case.
6. Jump to the next interesting time when the horizon is unbounded rather than iterating every unit.
7. 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.