ReviseAlgo Logo

Heaps & Priority Queues

Scheduling & Intervals

Master Heap scheduling algorithms: Meeting Rooms II interval triaging, and cooldown-based Task Scheduler logic.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What are Scheduling & Interval Problems?

Scheduling and Interval Problems require coordinating events (like meetings, computer processes, or printing tasks) that occupy specific spans of time. Heaps are used to monitor active resources dynamically:
  • Tracking when current resources will become free.
  • Prioritizing tasks with the highest demand or closest deadlines.

    • Why is it Important?

    Static lists cannot track overlapping timelines efficiently. A Priority Queue (Min-Heap) allows us to query which room, server, or resource will become vacant first in O(1) time.

    Where is it Used?

  • Cloud Load Balancers: Routing network requests to servers with the earliest completion times.
  • Calendar Software: Flagging double-booking meeting rooms.

    • 2. Mental Model: The Hotel Key Rack

    Imagine managing meeting rooms in an office:

  • When a group requests a room, you check a rack of keys (the Min-Heap).
  • Each key on the rack is labeled with the check-out/end-time of the meeting currently occupying it.
  • You look at the key with the earliest end-time (the root of the Min-Heap).
  • If that room's meeting has already finished before the new group starts, you hand them that key (pop the root, update its end-time, and push it back).
  • If the earliest room is still occupied, you must allocate a new room (push a new key onto the rack).

    • 3. Core Algorithms & Implementations

    1. Meeting Rooms II (Minimum Rooms Needed)

    Find the minimum number of conference rooms required to hold all meetings.
  • Algorithm: Sort meetings by start time. Initialize a Min-Heap storing meeting end times.
  • For each meeting m:
    • - If m.start >= heap.peek() (the earliest ending meeting is finished), pop the heap (we reuse that room). - Push m.end onto the heap (representing the room's new availability threshold). - The final size of the heap is the minimum number of rooms needed.

    2. Task Scheduler with Cooldown (LeetCode 621)

    Given char tasks (e.g. ['A', 'A', 'B']) and cooldown N, find the least CPU intervals to complete all tasks.
  • Algorithm: Store task frequencies in a Max-Heap. We always want to execute the highest-frequency task first.
  • If we execute a task, decrement its frequency. If it still needs to be run, place it in a temporary queue along with the CPU cycle index when it will be out of cooldown.
  • When the cooldown cycle passes, push the task back onto the heap.

    • 4. Visual Timeline: Meeting Rooms Allocation

    Trace showing room allocations for intervals [[0, 30], [5, 10], [15, 20]]:

    5. Real-World Examples

  • Server Load Triage: Dispatching compute threads to cloud instances with the minimum current workload.
  • Flight Gate Assignment: Allocating incoming planes to arrival gates at airport terminals dynamically.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test chronological order tracking:
  • "Given task intervals, find the maximum overlaps." -> In Meeting Rooms II, explain that sorting by start time is mandatory to make greedy allocations correct.
  • "Why does a queue pair with a heap in the Task Scheduler?" -> The heap chooses the next highest frequency task, while the queue holds tasks in cooldown until their cooldown timestamps match the running cycle time.

    • Common Mistakes

    Warning: 1. Forgetting to Sort by Start Time: Attempting to run meeting allocations on unsorted inputs will fail because you might process a later meeting before an earlier one, disrupting room availability calculations.
    > 2. Storing Start Times in the Heap: The heap must track end times (when rooms become free), not start times.

    7. Summary

  • Meetings: Sort by start time. Min-Heap tracks active meeting end times.
  • Tasks: Max-Heap prioritizes high-frequency tasks; queue manages cooldown timing.
  • Complexities: Meeting Rooms II is O(N log N) time / O(N) space; Task Scheduler is O(T log A) time (where A is alphabet size ≤ 26).

    • 8. Quiz

    Question 1: What occurs if a meeting's start time exactly equals the earliest end time in the heap? Answer: We can reuse that room. The condition start >= allocator.peek() is met, so we pop the old end time and push the new end time.
    Question 2: What is the maximum size of the priority queue in the Task Scheduler algorithm? Answer: At most 26 elements (for English capital letters A-Z). Because the heap size is bounded by a constant, heap operations are virtually O(1) complexity.
    Question 3: If meeting intervals are [[1, 5], [5, 10]], how many rooms are needed? Answer: 1. The second meeting starts at 5, which is ≥ the end time of the first meeting, letting us reuse the room.
    Question 4: True or False: Priority Queue allocations solve all scheduling problems optimally. Answer: False. While greedy heap allocations work for finding maximum overlaps (Meeting Rooms), NP-hard scheduling problems (like Bin Packing) require approximation algorithms or backtracking search.
    Question 5: Why is the cooldown queue implemented as a queue instead of another heap? Answer: Because tasks are added to the cooldown queue in chronological order of their availability times. A FIFO queue naturally preserves this temporal ordering.