Neel Mishra
← All Posts
DSA · Heaps · Part 10 of 17

Scheduling, Intervals & the Sweep

August 2026 · 22 min read

Interval and scheduling problems are where heaps stop being a data-structure exercise and start being the obvious tool. The recurring shape: events happen over time, resources are occupied and then released, and you must always know which resource frees up first. “Frees up first” is a minimum query over a changing set — a min-heap, every time.

Meeting Rooms II: The Archetype

Given intervals [start, end), find the minimum number of rooms needed so that no two overlapping meetings share a room.

The heap formulation is almost a restatement of the problem. Sort meetings by start time and keep a min-heap of the end times of currently occupied rooms. The root is the room that frees soonest — the only room worth checking:

#include <queue>
#include <vector>
#include <algorithm>

int minMeetingRooms(std::vector<std::vector<int>>& meetings) {
    if (meetings.empty()) return 0;

    std::sort(meetings.begin(), meetings.end());          // by start time

    std::priority_queue<int, std::vector<int>, std::greater<int>> endTimes;

    for (const auto& m : meetings) {
        if (!endTimes.empty() && endTimes.top() <= m[0])
            endTimes.pop();                               // a room freed in time: reuse it
        endTimes.push(m[1]);                              // occupy a room until m[1]
    }
    return (int)endTimes.size();                          // rooms held simultaneously
}

Why checking only the root suffices: if the earliest-ending meeting has not finished, no other room is free either. One comparison decides between reuse and allocation.

And why the answer is the final heap size: the heap only ever grows when no room could be reused, so its maximum size equals the peak concurrency — and because we pop at most one per iteration, the size never shrinks below that peak. O(n log n), dominated by the sort.

Half-open intervals matter. Use <= when a meeting ending at time t lets another start at t, and < when it does not. This one character is the difference between accepting and failing on the boundary test, and problem statements are often vague about it. Decide explicitly rather than guessing.

The Alternative: Sweep Line

The same problem without a heap. Split each interval into two events, sort them all, and sweep:

int minMeetingRooms(std::vector<std::vector<int>>& meetings) {
    std::vector<std::pair<int,int>> events;             // (time, +1 start / -1 end)
    for (const auto& m : meetings) {
        events.push_back({m[0], +1});
        events.push_back({m[1], -1});
    }
    std::sort(events.begin(), events.end());            // ends sort before starts at equal time

    int cur = 0, best = 0;
    for (const auto& e : events) { cur += e.second; best = std::max(best, cur); }
    return best;
}

Sorting (time, delta) pairs puts -1 before +1 at identical times, which encodes the half-open convention for free. This version is simpler and often faster.

So when is the heap worth it? When you need to know which resource, not merely how many. The sweep gives a count; the heap gives you the actual room, so you can assign an identifier, attach state to it, or report the schedule. Problems that ask you to output an assignment need the heap.

Task Scheduler with Cooldown

Identical tasks must be separated by at least n intervals of cooldown; minimise total time. This one needs the two-container arrangement from Part 9: a max-heap of what is runnable and a queue of what is cooling down.

#include <queue>
#include <unordered_map>

int leastInterval(std::vector<char>& tasks, int n) {
    std::unordered_map<char, int> count;
    for (char c : tasks) ++count[c];

    std::priority_queue<int> ready;                       // max-heap of remaining counts
    for (const auto& kv : count) ready.push(kv.second);

    std::queue<std::pair<int,int>> cooling;               // (remaining count, time it becomes ready)
    int time = 0;

    while (!ready.empty() || !cooling.empty()) {
        ++time;

        if (!cooling.empty() && cooling.front().second == time) {
            ready.push(cooling.front().first);            // cooldown expired
            cooling.pop();
        }

        if (!ready.empty()) {
            int remaining = ready.top() - 1;
            ready.pop();
            if (remaining > 0) cooling.push({remaining, time + n + 1});
        }
        // else: idle tick, nothing runnable
    }
    return time;
}

Greedily running the most frequent remaining task is what makes this optimal — the bottleneck is always the task with the highest count, so every tick spent on anything else while it is available wastes an opportunity to space it out. The max-heap enforces that choice, and the FIFO queue works because cooldowns all have the same duration and therefore expire in insertion order.

Single-Threaded CPU

Tasks have an enqueue time and a duration. The CPU always picks the shortest available task, breaking ties by index. Two structures again: sort by availability, and hold the available set in a heap keyed by (duration, index).

std::vector<int> getOrder(std::vector<std::vector<int>>& tasks) {
    int n = (int)tasks.size();
    std::vector<int> idx(n);
    for (int i = 0; i < n; ++i) idx[i] = i;
    std::sort(idx.begin(), idx.end(),
              [&](int a, int b) { return tasks[a][0] < tasks[b][0]; });

    using Job = std::pair<int,int>;                       // (duration, original index)
    std::priority_queue<Job, std::vector<Job>, std::greater<Job>> ready;

    std::vector<int> order;
    long long now = 0;
    int i = 0;

    while ((int)order.size() < n) {
        while (i < n && tasks[idx[i]][0] <= now) {        // admit everything that has arrived
            ready.push({tasks[idx[i]][1], idx[i]});
            ++i;
        }
        if (ready.empty()) {                              // CPU idle: jump to the next arrival
            now = tasks[idx[i]][0];
            continue;
        }
        auto [dur, id] = ready.top();
        ready.pop();
        now += dur;
        order.push_back(id);
    }
    return order;
}

Two things to steal. The time jump when the ready set is empty — advancing one tick at a time would be O(max_time) and time values are often up to 109. And now as long long, since n durations each up to 109 overflow int comfortably.

The Template

Nearly every scheduling problem in this family is:

  1. Sort by the time things become available (start time, enqueue time, arrival).
  2. Keep a heap of active or available items, keyed by whatever the selection rule is (end time, duration, profit, count).
  3. Advance a clock. At each step, admit newly available items into the heap, then take the heap's root.
  4. Jump, do not tick. When nothing is available, skip straight to the next event time.

The two-sorted-orders structure — one for availability, one for priority — is the signature. That is exactly why one sort plus one heap keeps appearing: you need two different orderings of the same data at the same time.

Practice