L48 · Intervals

Series: LeetCode — From Basics to Interview-Ready · Session 48 / 65 · Phase 3 · Advanced & specialised

Why this session exists

Every interval problem starts with a sort. That is the single most useful sentence in this session, and it is almost always true. Unsorted intervals are an unstructured pile where any pair might overlap; sorted intervals have the property that overlaps are local, so a single left-to-right pass sees everything it needs.

The second sentence is the one that separates people who have practised from people who have not: which key you sort by depends on the question. Merging wants sorting by start, because you build up a running merged interval and extend it as long as the next one begins before the current one ends. Scheduling — the "how many can I fit without conflict" family — wants sorting by end, because finishing early leaves the most room for whatever comes next. Getting this backwards produces plausible-looking code that fails on the third test case.

Meeting Rooms II is the third idea. Sorting alone answers "do any two overlap"; it does not answer "what is the maximum number overlapping at once". For that you need to track what is currently running, and a min-heap keyed on end time does it in one pass. The alternative — a sweep line over separated start and end events — is arguably simpler and worth knowing as well.

Four problems, three techniques, one sort. This session is dense but not deep, and it is one of the highest return-per-minute sessions in the entire series because the pattern appears constantly and the code is short.

Blank-file warm-up

Five minutes, empty file, no notes. Write the merge loop:

1. Sort by start.
2. The overlap test between the incoming interval and the last merged one.
3. The extension step, and the append step.

The overlap test is where people are imprecise. Write if current_start <= last_end — with the equals — and then decide deliberately whether touching intervals like [1,3] and [3,5] should merge. For Merge Intervals they should. For some scheduling problems they should not. Being deliberate about that boundary is the actual skill.

Pattern anatomy

The shape that summons this pattern: a collection of pairs representing ranges, and a question about how they relate — overlap, coverage, conflict, or count.

The invariant for merging: after processing the first k sorted intervals, the output list contains disjoint intervals covering exactly the union of those k, and the last element of the output is the only one that can still be extended. That second clause is why one pass suffices — sorting by start guarantees that nothing you have already closed off can be reopened.

def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])          # by START
    out = [intervals[0][:]]
    for start, end in intervals[1:]:
        if start <= out[-1][1]:                 # overlaps the running interval
            out[-1][1] = max(out[-1][1], end)   # max, NOT end
        else:
            out.append([start, end])
    return out

The max on the extension line is not optional. A fully contained interval like [2, 3] arriving after [1, 10] would otherwise shrink the merged range to [1, 3]. Sorting by start does not order the ends, so containment is always possible.

The scheduling variant sorts by end and greedily keeps whatever finishes soonest:

def erase_overlap_intervals(intervals):
    """Minimum removals so that the rest are non-overlapping."""
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])          # by END
    kept, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:                   # no conflict with what we kept
            kept += 1
            last_end = end
    return len(intervals) - kept

And the room-counting variant, which needs to know what is currently running:

import heapq
 
def min_meeting_rooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])          # by START
    rooms = []                                  # min-heap of end times
    for start, end in intervals:
        if rooms and rooms[0] <= start:
            heapq.heapreplace(rooms, end)       # reuse the earliest-freed room
        else:
            heapq.heappush(rooms, end)          # need a new room
    return len(rooms)

The heap holds the end time of every meeting currently in progress. Its root is the one finishing soonest, which is the only room that could possibly be free. If it is free, reuse it; otherwise open a new one. The final heap size is the peak concurrency.

The cue

You are looking at an interval problem when the statement contains these tells:

1. Input is a list of pairs interpretable as [start, end]. Meetings, bookings, ranges, segments, flights. If the two numbers of each pair describe a span, this is the family.
2. "Overlapping", "non-overlapping", "merge", "conflict", "cover". Direct vocabulary matches.
3. "Minimum number of rooms / platforms / machines". That is peak concurrency, which is the heap or sweep-line variant, not plain merging.
4. "Maximum number of activities you can attend." That is the classic activity-selection greedy — sort by end, take whatever fits. It is the single most reliable greedy in all of algorithms and it is worth knowing that it is provably optimal.
5. "Insert a new interval into a sorted list." Special case with an O(n) answer that skips the sort entirely, since the input is already ordered.

Tell 3 versus tell 4 is the distinction that matters most. Both mention scheduling; one wants a count of resources and the other wants a count of activities, and they use different sort keys and different machinery.

Guided solve

Merge Intervals — given a collection of intervals, merge all overlapping ones and return the disjoint result.

Start with why sorting is required rather than merely convenient. Unsorted, any interval might overlap any other, so checking all pairs is O(n²) and merging is not even well-defined as a single pass — merging two intervals can create a new one that now overlaps a third you already examined. Sorting by start eliminates that entirely: once you move past an interval, nothing arriving later can extend it backwards, because later intervals have larger or equal starts.

So sort by start. Now walk left to right maintaining one open interval, the last thing in your output list.

For each incoming interval, exactly one of two things is true. Either it starts at or before the open interval's end, in which case the two are connected and you extend the open interval's end to the maximum of the two ends. Or it starts strictly after, in which case there is a genuine gap, the open interval can never be extended again, and the new one becomes the open interval.

That is the whole algorithm. Six lines.

Now the details that decide whether it passes.

max on the extension. Covered above but worth repeating because it is the most common bug in this problem. Input [[1,10],[2,3],[4,5]] sorts to itself, and without the max you would produce [[1,5]] instead of [[1,10]].

The <= versus < decision. Should [1,3] and [3,5] merge into [1,5]? For Merge Intervals the standard answer is yes — they touch, and the union is contiguous. Use <=. For Meeting Rooms, a meeting ending at 3 and another starting at 3 do not conflict, so there you want strict inequality on the conflict test. Same geometry, opposite convention, driven entirely by whether the endpoints are inclusive.

Sorting stability and the secondary key. For merging you do not need a tie-break on the end, because the max handles any order of equal starts. For some problems you do. If two intervals share a start, ask yourself whether processing the longer one first changes anything before adding key=lambda x: (x[0], -x[1]).

Mutation. out.append(intervals[0]) without copying means you mutate the input array when you extend. Usually harmless, occasionally not, and it will confuse you during debugging. Copy the first element.

Trace [[1,3],[2,6],[8,10],[15,18]]. Sorted already. Output starts [[1,3]]. Next [2,6]: 2 <= 3 so extend to [1,6]. Next [8,10]: 8 > 6 so append, giving [[1,6],[8,10]]. Next [15,18]: 15 > 10 so append. Result [[1,6],[8,10],[15,18]].

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Insert Interval — the list is already sorted and disjoint. Do it in O(n) with no sort: three phases, the intervals entirely before the new one, the ones overlapping it which you absorb, and the ones entirely after. Think about the phase boundaries before writing.
• Non-overlapping Intervals — minimum removals to eliminate all overlaps. Sort by end. Be ready to argue why sorting by end is correct and sorting by start is not.
• Meeting Rooms II — minimum rooms. Heap or sweep line, your choice, but be able to describe the other one.

If those land early, do Interval List Intersections — two sorted lists, find every overlapping segment. Two pointers, and the intersection of [a,b] and [c,d] is [max(a,c), min(b,d)] when that is non-empty.

Common failure modes

Forgetting max when extending. Produces truncated merged intervals whenever one interval contains another. Test with [[1,10],[2,3]].

Sorting by the wrong key. Sorting by start for activity selection gives a greedy that looks reasonable and is wrong — a long early interval blocks several short later ones. Sorting by end for merging breaks the locality argument that makes one pass valid. Decide which question you are answering before you write the key.

Confusing "number of overlaps" with "maximum concurrent". Counting how many pairs overlap is a different question from how many are simultaneously active at the busiest moment. The second is what room-counting asks.

Inclusive/exclusive endpoint confusion. [1,3] and [3,5] merge in one problem and do not conflict in another. Read the statement for whether endpoints are inclusive and set your comparison operator deliberately, not by habit.

Not handling the empty input. intervals[0] on an empty list throws. One guard line.

Using a heap when a counter would do. If you only need the peak count and not the identity of the rooms, the sweep line is simpler and has a lower constant factor. The heap is not wrong, just heavier than necessary.

Complexity

Merge Intervals: O(n log n) time, O(n) space. The sort dominates; the merge pass is a single O(n) sweep. Space is the output list, plus whatever the sort uses — Python's Timsort is O(n) auxiliary in the worst case.

Insert Interval: O(n) time, O(n) space — no sort needed because the input is guaranteed sorted, which is the entire reason it is a separate problem from Merge Intervals.

Non-overlapping Intervals: O(n log n) time, O(1) extra space beyond the sort. One pass with two scalars.

Meeting Rooms II: O(n log n) time. Sort is n log n, and the heap does at most n pushes and n pops at log n each, so the heap work is also n log n. Space is O(n) for the heap in the worst case where every meeting overlaps every other. The sweep line is the same asymptotics with O(n) space for the two event arrays and a much smaller constant.

None of these can beat n log n in general, because a comparison-based algorithm that determines the merged structure can be used to sort, so the sorting lower bound applies.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Merge Intervals should sit at cold permanently after two clean passes. Meeting Rooms II deserves a shorter leash — the heap version has enough moving parts that it decays faster than the merge loop.