Intervals

Review boundary and corrected contracts

Closed intervals merge when endpoints touch; scheduling uses half-open intervals with strictly positive duration and touching meetings can reuse a room. The heap stores allocated-room latest end times, not only currently active meetings. Sorting mutates input and can use O(n) auxiliary storage.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own the merge loop cold, then learn the two sorting keys — by start for merging, by end for scheduling — and when each one is correct.

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

Prerequisites. Sorting with a custom key, and — for the Meeting Rooms II variant only — the size-K heap from L26. Everything else is derived here.

Watch first

Optional original pre-reads (links retained; availability and timestamps not rechecked):

• Merge Intervals — Leetcode 56 — Sort by start, then the six-line merge loop — the base case every other problem in this family builds on.
• Meeting Rooms II — Leetcode 253 — Peak concurrency rather than merging, and why a min-heap on end times answers it in one pass.
• Non-Overlapping Intervals — Leetcode 435 — The sort-by-END half of the session, and the greedy argument for why finishing early leaves the most room.

Why this session exists

Many offline interval problems begin by sorting. Already-sorted Insert Interval and Interval List Intersections do not need another sort. For unsorted merging, ordering by start makes the next possible extension local to the running interval.

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 more state: either allocated rooms and their latest end times, as in the heap below, or an active-meeting count, as in the sweep. 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.

Merging preserves all covered time; scheduling asks a different question: which intervals can we keep without conflict? Extending a merged range no longer helps that objective. Instead, sort by end and keep the compatible interval that finishes soonest, leaving the largest remaining stretch of the timeline available for later choices:

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

Room counting changes the objective again: no meeting may be discarded, so a conflict means allocating another room rather than rejecting an interval. Process meetings by start time and keep the latest assigned end time for each room. The earliest of those end times tells us whether any allocated room can be reused:

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 is a ledger of allocated rooms, not a list containing only meetings still in progress: a room's last end time stays in the heap even after that meeting finishes. Several rooms may already be free, but checking the earliest end is enough to decide whether at least one is available. Reuse that room by replacing its end time; allocate another only when even the earliest room is still busy. Because entries are reused rather than removed, the final heap size records the peak room requirement. The event sweep below instead counts active meetings directly, so it must remember the largest count reached.

The sweep-line alternative to the heap: split every interval into a start event and an end event, sort all events by time with end events ordered before start events at equal times, then walk them keeping a running counter — plus one on a start, minus one on an end. The maximum the counter reaches is the answer. It is O(n log n) like the heap version, uses no heap, and generalises immediately to "at what time was concurrency highest", which the displayed heap function does not record.

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 enables this particular one-pass merge. 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.

Insert Interval answer

For closed, start-sorted, pairwise disjoint input, copy intervals ending strictly before the new start; absorb intervals whose start is at most the growing new end; then copy the remaining suffix. The unprocessed suffix stays ordered, so no absorbed interval can be skipped. This version does not mutate either input.

def insert_interval(intervals, new_interval):
    start, end = new_interval
    out, i = [], 0
    while i < len(intervals) and intervals[i][1] < start:
        out.append(intervals[i][:])
        i += 1
    while i < len(intervals) and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    out.append([start, end])
    out.extend(pair[:] for pair in intervals[i:])
    return out

For [[1,2],[5,7]] and [2,5], both intervals are absorbed and the result is [[1,7]]; empty input returns the new interval. For the optional intersections exercise, emit [max(a,c), min(b,d)] when nonempty, then advance whichever interval ends first (both may advance on a tie). Its earlier end cannot intersect a future interval from the other disjoint list. For [[1,3],[5,7]] and [[2,6]], the answer is [[2,3],[5,6]].

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 an event sweep would do. Both solve peak counting in O(n log n) time. A sweep can be simpler to explain; relative runtime depends on implementation and input, not an established constant-factor ranking.

Myth: For activity selection — fitting the maximum number of non-overlapping intervals — you should greedily pick the shortest intervals first, since short ones leave the most room.

Why: Shortest-first is a natural instinct and it is wrong. Consider three intervals: [1, 10], [9, 11], and [10, 20]. The shortest is [9, 11] at length 2, and picking it blocks both of the others, yielding one activity. Picking by earliest end time selects [1, 10] first, then [10, 20], yielding two. The correct greedy is earliest-finishing, and the exchange argument proves it: given any optimal solution, replace its first activity with the globally earliest-finishing one. That swap never creates a conflict, because the replacement ends no later than what it replaced, so the solution stays valid and the same size. Repeating the argument transforms any optimal solution into the greedy one, so the greedy is optimal.

Steps 1: Because an interval is defined by two endpoints on a line, any two intervals either overlap or are separated by a gap — there is no third case.

Steps 2: Because sorting by start makes the start times non-decreasing, an interval that begins after the current running end must also begin after every earlier interval's end.

Steps 3: Because of that, once a gap is observed the running interval is final and can never be extended by anything later in the sorted order.

Steps 4: Because each interval is therefore examined exactly once and either extends the running interval or closes it, a single left-to-right pass is sufficient.

Steps 5: Because the pass is O(n) and the sort is O(n log n), the sort dominates the total cost.

Steps 6: The merge scan is linear after ordering. Python sorting can exploit existing order, so sorted input can take linear time overall; this is an algorithmic bound, not a measured runtime promise.

Picture: Highlighter strokes on a timeline. You sweep left to right with one pen down. As long as the next stroke starts before your pen lifts, you keep the pen down and drag it to whichever stroke reaches furthest right. The moment a stroke starts past where your pen currently is, you lift, move, and start a new stroke.

Trigger: Fires on any input shaped as pairs of numbers describing spans, with a question about overlap, coverage, or conflict.

Name: Min-heap of end times

Gain: Stores one latest end per allocated room. With (end, room_id) entries it can also return room assignments; end times alone do not identify rooms.

Cost: O(n) heap memory; log-factor per operation with real constant overhead; more moving parts to get right under pressure

Name: Sweep line over separated events

Gain: Two sorted event streams and a counter expose peak concurrency and its time without a heap.

Cost: Loses the identity of individual intervals — you know how many are active but not which; the tie-breaking rule at equal timestamps is an easy thing to get backwards

Pick: Use the sweep when the answer is a count or a time. Use a room-id heap when assignments matter. The online heap argument requires arrivals in nondecreasing start order; arbitrary out-of-order arrivals do not preserve this greedy allocation guarantee.

Memory hook — "merge by start, schedule by end, count with a heap"

One sentence covers the entire family, and each clause maps to a distinct problem type.

Merge by START. You are building a running union, and you need to know what arrives next in space. Sorting by start guarantees nothing later can extend an interval backwards, which is what makes one pass sufficient. The peg: "unions grow rightward, so order by where things begin."

Schedule by END. You are fitting as many non-conflicting activities as possible, or removing as few as possible. The greedy is always take the one that finishes earliest, because finishing early leaves the maximum remaining room and can never be worse. The peg: "finish first, fit more." This is provably optimal by an exchange argument — swap any optimal solution's first activity for the earliest-finishing one and it remains valid.

Count with a HEAP. In the displayed allocation algorithm, keep one latest end time per room. Replace the earliest end when that room is free; otherwise allocate another room. The final heap size is the peak requirement. A different active-meeting variant removes all expired ends before inserting the next end and must track the maximum heap size separately. For [[0,10],[1,2],[20,21]], the allocation heap finishes with two entries although only one meeting is active at time 20. The peg: "allocated-room ledger is not active-meeting count."

And the boundary peg, which is the one that actually costs submissions: "touching is merging but not conflicting." Intervals [1,3] and [3,5] do merge in Merge Intervals (use <=), and they do not conflict in Meeting Rooms (use <). Same geometry, opposite convention. Decide it explicitly, out loud, every time.

What reviewers actually ask

These practice problems progress from merging to concurrency; the list is a curriculum, not a measured hiring-frequency ranking.

• 56 · Merge Intervals (Medium) — Practice selection. Probing the sort-by-start pass and the max on the extension. Follow-up: escalates to 57 or to 253.
• 57 · Insert Interval (Medium) — Practice selection. Probing whether you notice the input is already sorted, so no sort is needed and the answer is O(n) in three phases.
• 435 · Non-overlapping Intervals (Medium) — Practice selection. Probing the sort-by-end greedy. Follow-up: "prove it" — give the exchange argument.
• 253 · Meeting Rooms II (Medium) — Practice selection. Probing peak concurrency. Follow-up: solve it again with a sweep line over separated start and end events, and compare.
• 252 · Meeting Rooms (Easy) — Practice selection. The warm-up: can any two conflict? Usually asked immediately before 253.
• 986 · Interval List Intersections (Medium) — Practice selection. Probing two-pointer traversal of two sorted interval lists rather than a single merge.
• 452 · Minimum Number of Arrows to Burst Balloons (Medium) — Practice selection. The same sort-by-end greedy as 435 wearing different vocabulary — a good test of whether you recognise the pattern or the wording.
• 1235 · Maximum Profit in Job Scheduling (Hard) — Practice selection. Weighted activity selection, where the greedy fails and you need DP plus binary search. Worth knowing exists.

A useful follow-up is 56 to 253: merge, then count the peak overlaps. The union alone loses multiplicity, so the second question needs a heap or sweep state.

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, O(n) space. After sorting, each meeting performs one heap push or replacement, costing O(log n) in the worst case. The event sweep has the same asymptotic bounds. Neither implementation has a universal constant-factor advantage.

Producing a sorted union of arbitrary comparison-ordered intervals has a sorting lower bound: disjoint point intervals encode an arbitrary list of keys. This does not apply to already-sorted Insert Interval, which is O(n), or automatically prove a lower bound for every counting variant.

You can now…

• Recognise an interval problem from pairs interpretable as start and end, and start by sorting.

• Choose the sort key from the question — start for merging, end for scheduling greedies.

• Write the six-line merge loop cold, with max on the extension and a copy of the first element.

• Decide the touching-endpoint convention deliberately: merge on <=, conflict on <.

• Give the exchange argument for why earliest-finish-first is optimal for activity selection.

• Solve peak concurrency with a min-heap of end times, and describe the sweep-line alternative.

• Skip the sort entirely for Insert Interval and handle it in three phases in O(n).

Quiz

Self-check (answer follows each question).

Q: Why does merging require sorting by start rather than by end?

A: Sorting by start guarantees that once you observe a gap, no later interval can extend the closed one backwards, since all later starts are at least as large. That locality is what makes a single pass valid. Sorting by end gives no such guarantee about starts.

Q: Why must the extension use max(out[-1][1], end) rather than just end?

A: Because sorting by start says nothing about the order of ends. An interval fully contained in the running one, such as [2,3] after [1,10], would otherwise shrink the merged range.

Q: For maximum non-overlapping activities, why is earliest-finishing correct and shortest-first wrong?

A: Earliest-finishing leaves the maximum remaining room, and an exchange argument shows any optimal solution can be transformed into it without loss. Shortest-first fails on [1,10], [9,11], [10,20] — it picks the short middle one and blocks both others.

Q: What does the min-heap contain in Meeting Rooms II, and what does its size mean?

A: In the displayed code, one latest assigned end time per allocated room, including rooms already free. Its size is the rooms allocated so far, and final size equals peak demand. An active-only heap instead pops all expired meetings and returns its maximum size, not its final size.

Q: Should [1,3] and [3,5] be merged? On what does the answer depend?

A: It depends on whether the endpoints are inclusive. For Merge Intervals they touch and are merged, so the test uses <=. For meeting scheduling, a meeting ending at 3 does not conflict with one starting at 3, so the conflict test uses strict inequality.

Q: Describe the sweep-line solution to Meeting Rooms II and one thing it gives you that the heap does not.

A: Sort start and end events, process ends before starts at the same time for positive-duration half-open meetings, and track the maximum active count and its timestamp. The displayed heap returns only a count, but can also record peak time when a new room is allocated; this is not an exclusive capability of sweeps.

Stretch: true

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.

• For unsorted offline intervals, choose the ordering from the objective. Reuse an existing sorted-input guarantee instead of sorting again.

• Sort by START to merge. Sort by END to schedule the maximum number of non-conflicting activities.

• Extend with max(last_end, end) — sorting by start says nothing about the order of ends.

• Peak concurrency needs a min-heap of end times or a sweep line, not just a merge pass.

• Earliest-finishing is provably optimal for activity selection by an exchange argument. Shortest-first is not.

• Decide < versus <= from whether endpoints are inclusive, deliberately, before writing the comparison.

Corrective source notes

• Sorting Techniques — Python 3.14.8 documentation — Python sorting preserves the order of elements that compare equal. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.