</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Greedy with a heap: walk time forward, admit, expire, take the top

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]]

Worked example: four events attended over four days

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 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 t may return at slot t + k, so it is barred for k - 1 slots.
  • Missing the impossible case. An empty heap with a non-empty cooldown queue means no valid arrangement exists.
  • Mishandling small or large k. With k <= 1 no spacing is needed, so return s. With k larger than the string, only an all-distinct string works, and the general code returns "" otherwise.

7. Key takeaways

  1. Admit, expire, then choose. Skipping either step before the choice breaks the greedy.
  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 get 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 start day when the heap is empty 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.

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.