Interval Problems in C++: One Sort, One Sweep, and a Heap When You Need It

Posted on by NY Comdori

Interval problems look like a family of tricks. They are one trick applied seven ways, and the trick fits in a sentence: sort by start time, and every question about overlap becomes a question about the element you just looked at.

Without the sort, “do any two of these overlap?” is a pairwise check over n² pairs. With it, an interval can only overlap the ones immediately around it, so one linear walk answers the question. Three of the seven problems below need nothing more than that walk. The other four need one extra structure — a heap — and the interesting part is exactly why the walk stops being enough.

This is the second of three posts on Joseph Choi’s sorting session deck. Part one covered the five algorithms and the merge step; this one covers intervals. Everything was compiled with -Wall -Wextra -fsanitize=undefined,address under both C++17 and C++20 and checked against brute force before the prose was written.

Two questions to ask before writing anything

Every problem in this post is decided by the answers to these, and getting them explicit first saves rewriting the loop twice.

1. Do touching intervals count as overlapping? Is [1,3] against [3,5] an overlap or not? This is not a matter of taste; each problem states it, and it decides whether your comparison is < or <=. Merge Intervals says merge them, so its test is intervals[i][0] <= result.back()[1]. Meeting Rooms says a meeting ending at 9 and one starting at 9 are fine, so its test is intervals[i][0] < intervals[i-1][1]. Same relationship, opposite operator, because the problems asked different questions.

2. Are you producing intervals, or counting them? If the output is a set of intervals — merged, inserted, intersected — a single sorted walk does it, because you only ever need the most recent one. If the output is a count of simultaneous intervals, the most recent one is not enough: you need to know how many are still open, and which will close first. That is what the heap is for, and it is the line that divides this post in half.

Part 1: one sort, one sweep

Meeting Rooms (LC 252, Easy, Premium)

Note: LC 252 is a LeetCode Premium problem, so viewing it needs a paid subscription. Given meeting intervals, return whether a person could attend all of them — that is, whether any two overlap.

The deck’s build-up is the right one: brute force checks every pair at O(n²), and then — what if the intervals were sorted?

bool canAttendMeetings(vector<vector<int>>& intervals) {
    sort(begin(intervals), end(intervals), [](const vector<int> &l, const vector<int> &r){
        if (l[0] == r[0]) return l[1] < r[1];
        return l[0] < r[0]; });
    for (int i = 1; i < (int)intervals.size(); ++i) if (intervals[i][0] < intervals[i-1][1]) return false;
    return true;
}

Once sorted by start time, any overlap must involve two adjacent intervals. That is the whole insight and it deserves a proof sketch, because it is what all seven problems rest on: if i and j overlap with i < j and they are not adjacent, then everything between them starts after i starts and before j starts, so it starts before i ends too — meaning it overlaps i, and that pair is adjacent. So checking neighbours is sufficient.

Note the comparator breaks ties on end time. For this problem it changes nothing — two meetings with the same start overlap regardless of order — but it makes the sort deterministic, which matters when you are debugging against a reference implementation rather than eyeballing output.

Merge Intervals (LC 56, Medium)

The deck asks the precise question first: given two intervals A and B, what is the condition to merge them? Answer — when A starts no later than B, and B starts at or before A ends. Sorting by start guarantees the first half, so only the second half needs testing.

vector<vector<int>> merge56(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    sort(begin(intervals), end(intervals), [](const auto &l, const auto &r){ return l[0] < r[0]; });
    vector<vector<int>> result = {intervals.front()};
    for (int i = 1; i < (int)intervals.size(); ++i) {
        if (intervals[i][0] <= result.back()[1]) { result.back()[1] = max(result.back()[1], intervals[i][1]); continue; }
        result.push_back(intervals[i]);
    }
    return result;
}

Extending rather than replacing is the subtlety. When a new interval overlaps, the merged end is max(result.back()[1], intervals[i][1]) and not simply intervals[i][1], because the new interval can be entirely inside the one you already have. On [[1,10],[2,3] the answer is [1,10]; take the new end blindly and you get [1,3] and silently lose seven units of coverage.

I added the empty guard. The deck writes result = {intervals.front()} straight away, which is undefined behaviour on an empty input and survives only because LC 56 guarantees at least one interval. That guarantee does not travel with the code when you paste it somewhere else.

Insert Interval (LC 57, Medium)

Same problem with a head start: the list is already sorted and non-overlapping, and you are adding one interval. The deck’s route is to find the insertion point — it even asks “binary search?” — put the interval there, and then run Merge Intervals over the result.

vector<vector<int>> insert57(vector<vector<int>>& intervals, vector<int>& newInterval) {
    auto it = lower_bound(begin(intervals), end(intervals), newInterval[0],
                          [](const vector<int> &elt, int val){ return elt[0] < val; });
    intervals.insert(it, newInterval);
    vector<vector<int>> result; result.push_back(intervals[0]);
    for (int i = 1; i < (int)intervals.size(); ++i) {
        if (intervals[i][0] <= result.back()[1]) result.back()[1] = max(result.back()[1], intervals[i][1]);
        else result.push_back(intervals[i]);
    }
    return result;
}

The answer to the deck’s question is yes, and std::lower_bound with a projecting comparator does it. Worth being clear-eyed about what that buys, though: the search is O(log n), but vector::insert shifts every later element, so the insertion is O(n) and the merge pass after it is another O(n). The binary search is not making the solution faster — it is O(n) either way — it is making the intent explicit.

The textbook O(n) version skips the insert entirely: copy intervals that end before the new one starts, absorb every interval that overlaps it into a running merged interval, push that, then copy the rest. It avoids mutating the input, which this version does. If an interviewer asks for the single-pass form, that is the one they mean.

One detail that makes this version safe: result.push_back(intervals[0]) would be a bounds violation on an empty list, but intervals has just had newInterval inserted into it, so it always holds at least one element. The safety comes from the line above it, not from the problem’s constraints.

Interval List Intersections (LC 986, Medium)

Two already-sorted, non-overlapping lists; return every pairwise intersection. The deck says two pointers, and this is where the interval family meets the merge step from part one — it is the same walk, with an intersection computed instead of a value copied.

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> intersection; int i = 0, j = 0;
    while (i < (int)A.size() && j < (int)B.size()) {
        int s = max(A[i][0], B[j][0]), e = min(A[i][1], B[j][1]);
        if (s <= e) intersection.push_back({s, e});
        if (A[i][1] < B[j][1]) ++i; else ++j;
    }
    return intersection;
}

Two lines carry it. The intersection of two intervals is [max of the starts, min of the ends], which is non-empty exactly when start <= end — worth committing to memory, because it is the same formula every time and it is easy to get backwards under pressure.

Then: advance whichever interval ends first. Not the one that starts first — the one that ends first, because it is the one that can have no further intersections. Advancing on start time instead is the standard way to lose this problem, and it fails on exactly the case where one long interval overlaps several short ones.

Part 2: when one sweep is not enough

Now the problems change shape. The deck’s slide on Meeting Rooms II opens with “not just a sorting problem,” and that is the honest summary of the rest of this post.

Here is why. In Part 1 the only thing you ever needed from the past was the most recent merged interval, because merging is associative — once two intervals are combined they behave as one. Counting concurrency is different. To know how many meetings are running right now you have to know how many of the ones you have seen are still running, and that depends on their end times, which are in no particular order after a sort by start.

So you need a structure that answers one question fast: of everything currently open, which closes first? That is a min-heap on end time, and once you see that, the last three problems are the same program.

Meeting Rooms II (LC 253, Medium, Premium)

Note: Premium. Return the minimum number of conference rooms required — which the deck is careful to point out is not the number of meetings, and is the maximum number that ever overlap at one instant. Its example: A ends at 9am and B starts at 9am, so one room suffices.

int minMeetingRooms(vector<vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end(), [](const auto &l, const auto &r){ return l[0] < r[0]; });
    auto comp = [](const vector<int> &l, const vector<int> &r){ return l[1] > r[1]; };
    priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> pq(comp);   // (comp) is required pre-C++20
    pq.push(intervals.front());
    int numRooms = 1;
    for (int i = 1; i < (int)intervals.size(); ++i) {
        if (intervals[i][0] >= pq.top()[1]) pq.pop();
        pq.push(intervals[i]);
        numRooms = max(numRooms, (int)pq.size());
    }
    return numRooms;
}

Sort by start, keep a min-heap of end times. For each meeting, if it starts at or after the earliest end time in the heap, that room has freed up — pop it. Then push the new meeting. The heap size is the number of rooms in use, and the answer is the maximum that size ever reaches.

The deck asks its sharpest question here: pop only once — why? Because you are measuring the size of the heap, and you are adding exactly one meeting. Popping two rooms and pushing one would shrink the heap below the true concurrency. You only ever need to free one room per arriving meeting, since one arrival can only occupy one room. Popping in a loop would still give the right answer here (the max is taken over time), but it destroys the invariant that heap size equals rooms in use, and the next problem shows why that matters.

I changed one thing from the deck, and it is not cosmetic. The deck writes:

auto comp = [](const vector<int> &lhs, const vector<int> &rhs) {
    return lhs[1] > rhs[1];
};
priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> pq;   // no (comp)

That does not compile under C++17. A lambda’s closure type had no default constructor before C++20, so decltype(comp) as the comparator template argument needs an actual comp passed to the constructor. I confirmed it both ways: GCC rejects it with -std=c++17 and accepts it with -std=c++20. The deck’s own Employee Free Time slide passes pq(comp) correctly — it has to, because that lambda captures — so the two slides are inconsistent, and the inconsistent one only works because LeetCode’s toolchain is new enough.

Car Pooling (LC 1094, Medium)

The deck calls this very similar to Meeting Rooms II with a capacity check, and that is right — but the difference is instructive.

bool carPooling(vector<vector<int>>& trips, int capacity) {
    sort(begin(trips), end(trips), [](vector<int> &l, vector<int> &r){
        if (l[1] == r[1]) return l[2] < r[2];
        return l[1] < r[1]; });
    auto comp = [](vector<int> &l, vector<int> &r){ return l[2] > r[2]; };
    priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> pq(comp);
    pq.push(trips[0]);
    int numPassengers = trips[0][0];
    if (numPassengers > capacity) return false;
    for (int i = 1; i < (int)trips.size(); ++i) {
        while (!pq.empty() && pq.top()[2] <= trips[i][1]) { numPassengers -= pq.top()[0]; pq.pop(); }
        numPassengers += trips[i][0];
        if (numPassengers > capacity) return false;
        pq.push(trips[i]);
    }
    return true;
}

Here the pop is a while, not an if. That is the direct consequence of the deck’s “pop only once” question. In Meeting Rooms II you are counting rooms, so one arrival frees at most one; here you are tracking a running sum of passengers, and every trip that has already ended must give its seats back before you can judge the new one. Miss even one and the running total is too high and you reject a valid schedule.

The comparisons are also worth reading closely. The sort is on trips[i][1] — the start location — because LC 1094’s triples are {passengers, from, to}, so index 1 is the start and index 2 the end. And the release test is pq.top()[2] <= trips[i][1]: a passenger getting off at the exact point another gets on frees the seat, which is the same touching-intervals decision from the top of this post, answered the same way as Meeting Rooms.

Employee Free Time (LC 759, Hard, Premium)

Note: Premium. Each employee has a sorted, non-overlapping list of busy intervals. Return the intervals where everyone is free.

The deck reasons to the answer in three steps, and it is the cleanest bit of problem decomposition in the deck: to find free time you need the combined busy time; to combine busy time you must merge all the schedules; to merge them efficiently you need them in order, earliest first. What structure gives you that? A priority queue.

class Interval { public: int start, end; Interval(){} Interval(int s,int e):start(s),end(e){} };
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
    auto comp = [&schedule](pair<int,int> &lhs, pair<int,int> &rhs) {
        const Interval &l = schedule[lhs.first][lhs.second];
        const Interval &r = schedule[rhs.first][rhs.second];
        if (l.start == r.start) return l.end > r.end;
        return l.start > r.start;
    };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(comp)> pq(comp);
    for (int i = 0; i < (int)schedule.size(); ++i) pq.push(pair<int,int>(i, 0));
    vector<Interval> workingTime, freeTime;
    while (!pq.empty()) {
        pair<int,int> p = pq.top(); pq.pop();
        int employeeIdx = p.first, scheduleIdx = p.second;
        const Interval &i = schedule[employeeIdx][scheduleIdx];
        if (!workingTime.empty() && i.start <= workingTime.back().end)
            workingTime.back().end = max(workingTime.back().end, i.end);
        else {
            if (!workingTime.empty()) freeTime.push_back({workingTime.back().end, i.start});
            workingTime.push_back(i);
        }
        if (scheduleIdx < (int)schedule[employeeIdx].size() - 1) pq.push(pair<int,int>(employeeIdx, scheduleIdx + 1));
    }
    return freeTime;
}

The heap holds one (employee, index) cursor per employee, ordered by the start time of the interval each cursor points at. Pop the earliest, merge it into the running busy list exactly as in Merge Intervals, and push that employee’s next interval. This is a k-way merge — the generalisation of part one’s two-pointer merge to many sorted lists — and it is the reason the deck placed Intersection of Three Sorted Arrays earlier in the session.

Note that the heap never holds more than one interval per employee, so it is O(k) space for k employees rather than O(total intervals). The cost is O(n log k), which is the standard k-way merge bound and strictly better than concatenating everything and sorting when k is small relative to n.

The gap is recorded at the moment a popped interval does not overlap the running busy interval: the free time is {workingTime.back().end, i.start}. The !workingTime.empty() check before that is what stops you emitting a spurious free interval before the very first busy block — there is no “free time” before anyone has started.

And the comparator has to be passed to the constructor here, not just named as a template argument, because it captures schedule. A capturing lambda has no default constructor in any C++ standard, so this is the one place where the deck could not have taken the shortcut it took in Meeting Rooms II.

The seven problems on one page

ProblemSort byTouching counts as overlap?Extra structureWhat you track
252 Meeting Roomsstart, then endNo — <nonethe previous interval
56 Merge IntervalsstartYes — <=nonethe last merged interval
57 Insert Intervalalready sortedYes — <=nonethe last merged interval
986 Intersectionsalready sortedYes — <=nonetwo cursors
253 Meeting Rooms IIstartNo — >= frees a roommin-heap of endsheap size
1094 Car Poolingstart locationNo — <= frees seatsmin-heap of endsrunning passenger sum
759 Employee Free Timeheap-orderedYes — <=min-heap of k cursorsthe last merged busy interval

The third column is where these problems actually differ from one another. The fourth is where the post divides.

Misfits, edge cases, and the things that bite

The comparator trap that C++20 hides

Covered above, and it is the one genuinely portable-versus-not finding in this deck. priority_queue<T, C, decltype(comp)> pq; with no constructor argument compiles under C++20 and fails under C++17, because capture-less lambdas only became default-constructible in C++20. Verified in both modes.

If you want code that does not depend on the standard version, pass the comparator: pq(comp). It costs four characters and works everywhere. This is also a good reason to know which standard your judge is on — a solution that compiles on LeetCode and fails in your own project is a confusing hour.

Touching intervals decide your operator, and the problem decides touching

There is no universal answer to whether [1,3] and [3,5] overlap, and the seven problems above split roughly evenly. Merge Intervals merges them. Meeting Rooms does not consider them a conflict. Car Pooling frees the seat. Interval List Intersections reports [3,3] as a valid intersection of length zero — and LC 986’s own example output contains [5,5] and [24,24], which is the problem telling you its answer to the question.

Practical rule: before writing the loop, find the sample input where two intervals touch and read what the expected output does with it. If the samples do not contain one, that is worth an explicit question in an interview.

Pop once or pop while

Meeting Rooms II pops at most one entry per arrival; Car Pooling pops in a loop. Both are correct for their own problem and wrong for the other’s, and the deciding question is what you are measuring. A count of concurrent items tolerates a single pop because one arrival needs one slot. A running sum does not, because every departed item is still contributing to the total until you remove it.

Ask yourself: if three trips ended before this one starts, does my accumulator still contain their contribution? If yes, the pop has to be a while.

Advance the one that ends first

In LC 986 the pointer to advance is chosen by comparing end times, not start times. The interval that ends first is the one that cannot intersect anything further along the other list, so it is the only one that is safe to discard. Comparing starts instead passes the two-interval sample cases and fails as soon as one long interval spans several short ones.

Extend, do not replace

result.back()[1] = max(result.back()[1], intervals[i][1]). The max exists because the incoming interval may be fully contained in the current one. This is the most common Merge Intervals bug, it only shows up on nested intervals, and [[1,10],[2,3]] is the two-element input that catches it.

When the heap is the wrong structure

Meeting Rooms II and Car Pooling both have a second solution that is often simpler: the difference array or sweep line. Record +1 at every start and −1 at every end, sort the events, and take a running sum — the maximum of that sum is the answer. For Car Pooling, where locations are capped at 1,000, you can skip sorting entirely and bucket the deltas into a fixed array for an O(n + range) solution.

Reach for the heap when you need to know which interval is closing, or when you are merging k sorted lists. Reach for the difference array when you only need the count. Employee Free Time genuinely needs the heap; the other two do not, and the sweep-line version is shorter.

Two other boundaries worth knowing. If intervals are being inserted and queried repeatedly rather than processed in one batch, no amount of sorting helps — that is an interval tree or a segment tree. And if you need the union length rather than the union itself, you can accumulate it during the merge sweep without materialising the merged list at all.

How to practise this

  1. Answer the two questions at the top before writing code: does touching count, and am I producing intervals or counting them?
  2. Memorise the intersection formula — [max(starts), min(ends)], non-empty when start <= end. It never changes.
  3. Test [[1,10],[2,3]] for nesting and [[1,3],[3,5]] for touching, every time. Those two inputs catch most of the misfits above.
  4. For anything with a heap, state out loud what the heap size means. If you cannot, the pop logic will be wrong.
  5. In order: 252 → 56 → 57 → 986 → 253 → 1094 → 759. The first four are one walk; 253 introduces the heap; 1094 is 253 with a sum; 759 is the k-way generalisation.

The rest of this series

Credit and the rest of the series

The problem selection, the ordering, and the framing come from Joseph Choi‘s sorting session deck — including the “what if the intervals were sorted?” build-up for LC 252, the precise merge condition for LC 56, the three-step decomposition of Employee Free Time, and the “pop only once, why?” question that turns out to be the difference between LC 253 and LC 1094. The C++ here is my own, rewritten where I preferred an added guard or a portable comparator, and every listing was compiled and differentially tested before publication.

Other pattern write-ups on this site: