Interval Merging

Interval merging is the family of array-greedy problems where the input is a list of intervals [start, end] and the output requires reasoning about their overlaps. The canonical problem is LeetCode 56 (Merge Intervals): collapse a list of (possibly overlapping) intervals into the minimal list of non-overlapping intervals whose union is identical. The standard solution is a one-line greedy — sort by start time, sweep left-to-right, merge with the running last interval whenever the next interval starts at or before its end. Total time is O(n log n) (sort-dominated). The same greedy template extends to LC 57 (insert interval), LC 252/253 (meeting rooms), LC 1288 (covered intervals), and LC 986 (interval intersections), with small twists in the merge or compatibility predicate. The technique generalizes to sweep-line algorithms in computational geometry, which handle arbitrary interval-event problems by processing time-sorted endpoints.

1. Intuition — Painters Touching Up Walls

Imagine a list of painter work-orders, each saying “I worked from time start to time end on a wall.” Two painters whose intervals overlap or touch were effectively painting back-to-back; for billing purposes, you want to collapse the overlapping orders into a single “the wall was being painted from min(starts) to max(ends)” entry.

The natural way is to sort the orders by start time, then walk the list keeping a “currently being painted” interval. Each new order either (a) starts during the current paint job — extend the end if it ends later, otherwise just absorb it; or (b) starts after the current paint job ended — close out the current order and begin a new one.

This sweep-and-merge pattern is the entire algorithm. It works because the sort guarantees we never “miss” an overlap by processing a later-starting interval before an earlier-starting one. The merge condition (new.start ≤ current.end) is the test for “does this new interval touch or overlap the current one.” If yes, fuse; if no, emit and reset.

Compare to Activity Selection: that problem also walks sorted intervals greedily, but the goal there is maximum non-overlapping count (sort by finish time, skip overlaps), whereas merging is minimum-cardinality union (sort by start time, fuse overlaps). The two greedies have the same shape but different sort keys and different actions on conflict.

2. Tiny Worked Example

Input intervals (LeetCode 56 example):

[[1,3], [2,6], [8,10], [15,18]]

Step 1: sort by start time. (Already sorted; start times are 1, 2, 8, 15.)

Step 2: sweep.

Step	Current interval	Next interval	Decision
init	—	[1,3]	start: result = 1,3
1	[1,3]	[2,6]	2 ≤ 3 → overlap. Merge: end = max(3,6) = 6. Now [1,6].
2	[1,6]	[8,10]	8 > 6 → disjoint. Close [1,6], open [8,10]. result = [[1,6], [8,10]].
3	[8,10]	[15,18]	15 > 10 → disjoint. Close [8,10], open [15,18]. result = [[1,6], [8,10], [15,18]].

Output: [[1,6], [8,10], [15,18]]. Three intervals (down from four), no overlaps remain.

A second example, where multiple consecutive overlaps cascade:

Input:  [[1,4], [4,5]]
Sort:   [[1,4], [4,5]]   (already sorted)

  current = [1,4]
  next [4,5]: 4 ≤ 4 → overlap (touching counts!). Merge: end = max(4,5) = 5. Now [1,5].

Output: [[1,5]]

Note the ≤ vs < subtlety: with ≤, intervals [1,4] and [4,5] merge to [1,5]. With <, they would stay separate. LeetCode 56 specifies that touching intervals do merge (the problem statement uses <=). Always check the convention; see §10.3.

3. Pseudocode

merge_intervals(intervals):                 # list of (start, end)
    if intervals is empty:
        return []

    sort intervals by start ascending
    merged := [ intervals[0] ]              # seed with first

    for (s, e) in intervals[1:]:
        last_s, last_e := merged[-1]
        if s <= last_e:                     # overlap or touch
            merged[-1] := (last_s, max(last_e, e))
        else:
            merged.append( (s, e) )

    return merged

The structural points: (a) the result list is built in place by appending or extending the last entry; (b) the merge takes max(last_end, new_end) because a new interval can be entirely inside the current one (don’t shrink the end!); (c) we iterate intervals[1:] after seeding merged with intervals[0] to avoid an empty-list special case inside the loop.

4. Python Implementation

def merge_intervals(intervals):
    """LC 56. Collapse overlapping intervals into the minimal non-overlapping union.
 
    intervals: list of [start, end] pairs (inclusive endpoints; touching merges).
    Returns: list of merged [start, end] pairs in start-time order.
    """
    if not intervals:
        return []
 
    # Sort by start; ties broken by end (any consistent tie-break works).
    intervals.sort(key=lambda iv: iv[0])
 
    merged = [list(intervals[0])]    # mutable copy so we can extend its end
    for s, e in intervals[1:]:
        last = merged[-1]
        if s <= last[1]:             # overlap or touch
            last[1] = max(last[1], e)
        else:
            merged.append([s, e])
 
    return merged
 
 
# Sanity checks
assert merge_intervals([[1,3],[2,6],[8,10],[15,18]]) == [[1,6],[8,10],[15,18]]
assert merge_intervals([[1,4],[4,5]]) == [[1,5]]                  # touching merges
assert merge_intervals([[1,4],[2,3]]) == [[1,4]]                  # contained
assert merge_intervals([]) == []

The implementation is six lines plus boilerplate. Note merged = [list(intervals[0])] (not [intervals[0]]) — we want a mutable copy of the first interval so we can extend its end without modifying the caller’s list.

5. Why the Greedy Works — Exchange-Argument Proof

Theorem. The “sort by start, sweep, merge on overlap-or-touch” algorithm produces the unique minimum-cardinality list of non-overlapping intervals whose union equals the input’s union.

The proof is short because the output is uniquely determined by the input — there’s only one minimal partition of a set of intervals into non-overlapping maximal pieces.

Step 1: Output is a valid partition. By construction, every input interval is contained in some merged output interval (either it directly seeded one, or it was merged in). And no two output intervals overlap or touch (between any two consecutive merged intervals there’s a gap, by the greedy’s “if s > last_e, start new” rule). So the output is a partition of the input’s union into disjoint (non-touching) intervals.

Step 2: Output is minimum-cardinality. Suppose for contradiction some other valid partition P' has fewer intervals than the greedy’s output G. Consider the leftmost output interval [a, b] in G. Its starts come from some sorted-by-start prefix of the input, all of which were merged into [a, b] because each one’s start was ≤ the running end. This means the union of those input intervals is exactly [a, b] (the greedy’s running end never decreased, so the maximum end achievable while staying connected is b).

Now P' must cover [a, b], but if P' has fewer intervals than G does over the prefix that built [a, b], then P' has at most one interval in the union [a, b] — but that’s exactly what G has too! By induction on the rest of the input, |P'| ≥ |G|, contradicting the assumption.

Exchange argument framing. More cleanly: take any valid partition P'. Each P'-interval can be replaced one-for-one with the corresponding G-interval over the same span (they agree on extent — both cover the same input union maximally). So |P'| = |G|, meaning the greedy’s output is uniquely the minimum-cardinality answer. ∎

The interview-grade insight: the output is unique up to a re-ordering, so any correct algorithm produces the same intervals. The greedy is just the cheapest constructive route to that unique answer.

6. Complexity

6.1 Time — O(n log n)

• Sort by start time: O(n log n) — dominant.
• Sweep: O(n) — one pass, constant work per interval.
• Total: O(n log n).

If the input is already sorted by start (e.g., the events come from a time-stream), the sweep alone is O(n). This matters in production: in many real systems intervals arrive in start-time order naturally (event logs, scheduled jobs), and the sort can be skipped.

6.2 Space — O(1) extra (or O(n) if you can’t mutate)

The merged list is O(n) in the worst case (when no intervals overlap, the output equals the input). Excluding the output, the working memory is O(1) — we track only the running last interval. If the sort is in-place (Python’s list.sort is), we don’t add O(n) for sorting either.

If the input must remain unchanged, use sorted(intervals, …), which copies — that’s O(n) extra.

7. Variants — The Family of Interval Problems

7.1 LC 57 — Insert Interval (Pre-sorted Input)

The input is already sorted and non-overlapping. Insert a new interval [s, e] and re-merge into the minimum non-overlapping list. The straightforward approach is to append [s, e] and run the LC 56 algorithm — O(n log n). But because the input is sorted, an O(n) solution is possible:

def insert_interval(intervals, new_iv):
    """LC 57. Insert into a sorted, non-overlapping interval list.
 
    Three-phase scan: copy intervals strictly before new, merge overlapping ones, copy after.
    """
    result = []
    s, e = new_iv
    i, n = 0, len(intervals)
 
    # Phase 1: intervals ending before `new` starts — copy as-is.
    while i < n and intervals[i][1] < s:
        result.append(intervals[i])
        i += 1
 
    # Phase 2: intervals overlapping `new` — merge into [s, e].
    while i < n and intervals[i][0] <= e:
        s = min(s, intervals[i][0])
        e = max(e, intervals[i][1])
        i += 1
    result.append([s, e])
 
    # Phase 3: intervals starting after `new` ends — copy as-is.
    while i < n:
        result.append(intervals[i])
        i += 1
 
    return result

The insight: since input is sorted and disjoint, the new interval’s overlap region is a contiguous block. The three-phase scan handles before / merge / after in a single linear pass — O(n).

7.2 LC 252 — Meeting Rooms (Can Anyone Attend?)

Given a list of meetings, can a single person attend all of them (no overlaps)?

def can_attend_all_meetings(intervals):
    """LC 252. True iff no two intervals overlap."""
    intervals.sort(key=lambda iv: iv[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:
            return False
    return True

O(n log n). Sort by start; check consecutive pairs for overlap. The “touching is allowed” convention here means we use < (strict) rather than <=.

7.3 LC 253 — Meeting Rooms II (Minimum Rooms Needed)

The harder cousin: how many rooms are needed to schedule all meetings? Equivalently, what’s the maximum overlap depth? Two clean solutions:

Solution A — Min-heap (sweep by start, evict by earliest end):

import heapq
 
def min_meeting_rooms(intervals):
    """LC 253. Minimum number of rooms to schedule all meetings."""
    if not intervals:
        return 0
    intervals.sort(key=lambda iv: iv[0])
    rooms = []                                      # min-heap of end times
    heapq.heappush(rooms, intervals[0][1])
    for s, e in intervals[1:]:
        if rooms[0] <= s:                          # earliest-ending room is free
            heapq.heappop(rooms)
        heapq.heappush(rooms, e)
    return len(rooms)

The heap holds the end times of currently-busy rooms. For each new meeting, if the soonest-ending room is free (rooms[0] <= s), we reuse it (pop + push). Otherwise we open a new room (just push). The final heap size is the total rooms needed. O(n log n).

Solution B — Two-pointer sweep on separate start/end arrays:

def min_meeting_rooms_two_pointer(intervals):
    starts = sorted(s for s, _ in intervals)
    ends   = sorted(e for _, e in intervals)
    rooms = peak = 0
    j = 0
    for s in starts:
        while j < len(ends) and ends[j] <= s:
            rooms -= 1
            j += 1
        rooms += 1
        peak = max(peak, rooms)
    return peak

Process events in time order: each start increments the room count, each end decrements. The maximum count ever observed is the answer. O(n log n) (sort dominates), O(1) extra space if the original lists can be sorted in place.

This is the sweep-line technique in disguise — see §8.

7.4 LC 1288 — Remove Covered Intervals

Count intervals not strictly contained in another interval. Sort by (start ascending, end descending) — so for ties on start, the wider interval comes first. Then sweep: an interval is “covered” iff its end ≤ the maximum end seen so far.

def remove_covered_intervals(intervals):
    """LC 1288. Count of intervals NOT covered by any other."""
    intervals.sort(key=lambda iv: (iv[0], -iv[1]))
    count = 0
    max_end = 0
    for _, e in intervals:
        if e > max_end:
            count += 1
            max_end = e
    return count

The (start asc, end desc) sort is the trick: it ensures that when intervals share a start, the widest one is processed first. Then the strict-greater check e > max_end catches intervals that genuinely extend the right boundary (uncovered) versus those that don’t (covered). O(n log n).

7.5 LC 986 — Interval List Intersections (Two-Pointer)

Given two sorted, disjoint interval lists A and B, return their pairwise intersection list.

def interval_intersection(A, B):
    """LC 986. Intersect two sorted, disjoint interval lists."""
    i = j = 0
    result = []
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi:                       # actual intersection (touching counts)
            result.append([lo, hi])
        if A[i][1] < B[j][1]:               # advance the one ending first
            i += 1
        else:
            j += 1
    return result

Total time O(|A| + |B|). The two-pointer pattern is standard for “merge two sorted streams”-shaped problems; the only twist is that we emit the intersection of the current pair, not the union. The advance rule (advance the interval that ends first) is correct because once an interval has ended, it can’t intersect anything later in the other list.

8. Comparison with Sweep-Line

The interval-merge algorithm is a degenerate sweep-line — a generic computational-geometry technique where you process events in sorted order along an axis (here, time; in geometry, often x-coordinate). The full sweep-line treatment (see Bentley-Ottmann 1979 for line-segment intersection, or de Berg et al., Computational Geometry, Ch. 2) is:

1. Event queue. A priority queue of events sorted by sweep position. For interval problems, the events are “interval starts” (insert) and “interval ends” (remove).
2. Status structure. A balanced BST of currently-active intervals, keyed for fast lookup of overlapping members.
3. Event handling. Process the next event, update the status, possibly emit output.

For the simple “merge overlapping intervals” problem, the status structure degenerates to a single variable (the running end), and the event queue is just the sorted input. The full sweep-line apparatus is overkill here — but it’s the same idea, generalized. When you encounter problems that need to handle insertions during the sweep (new intervals arriving), or when intervals are points in higher-dimensional space, the full sweep-line technique becomes necessary.

For LC 253 (meeting rooms II), the two-pointer sweep on separate start/end arrays is the cleanest “real” sweep-line in interview problems — you’re literally processing time-sorted events. Recognize the pattern: any problem about “max concurrent X” tends to be a sweep-line problem.

9. Common Interview Problems

LeetCode #	Title	Twist
56	Merge Intervals	The canonical problem
57	Insert Interval	Pre-sorted; O(n) three-phase scan
252	Meeting Rooms	Can-attend-all? Boolean answer
253	Meeting Rooms II	Min rooms = max overlap depth
1288	Remove Covered Intervals	Sort by (start asc, end desc)
986	Interval List Intersections	Two-pointer on two sorted lists
435	Non-overlapping Intervals	Activity-selection cousin (sort by end)
452	Minimum Number of Arrows	Activity-selection cousin
1094	Car Pooling	Sweep-line with cumulative count
759	Employee Free Time	Merge K sorted lists, then complement

10. Pitfalls

10.1 Wrong Sort Key

Sort by start time for merging. Sort by finish time for activity selection (max non-overlapping count). These are different problems with different greedies that look similar; mixing them up gives subtly wrong answers. The diagnostic question: “am I trying to minimize union pieces (merge) or maximize disjoint count (select)?“

10.2 Forgetting max(last_end, new_end)

The merge step is last.end = max(last.end, new.end), not last.end = new.end. Containment is the trap: if the new interval ends before the current one (e.g., merging [1,10] with [2,5]), naively setting last.end = new.end shrinks the merged range from [1,10] to [1,5], dropping coverage of [5,10]. Always take the max.

10.3 < vs <= (Touching Intervals)

LeetCode 56 says intervals [1,4] and [4,5] should merge to [1,5] — touching counts as overlap. So the merge condition is s <= last_end, with <=. Other problems treat touching as disjoint (closed intervals don’t conflict at endpoints). Always check the problem statement; the convention is not universal. For LC 252 (meeting rooms), touching is allowed (one meeting ending at exactly the same time another starts is fine), so the conflict test is < (strict).

10.4 Modifying the Input

intervals.sort(...) mutates the caller’s list. If the caller still expects the original order, use sorted(intervals, ...) instead — copies cost O(n) but preserve the contract.

10.5 Empty Input

return [] for empty input is the standard. The seed-and-iterate pattern (merged = [intervals[0]]) crashes on empty input — guard with an early return.

10.6 Integer Overflow on Large Endpoints

Not a concern in Python (arbitrary precision), but in C++/Java with 32-bit int endpoints, start + duration arithmetic can overflow. For interval problems with bounds near INT_MAX, use long/int64. LeetCode tests have hit this on at least one interval problem (verify on the specific problem).

10.7 Tie-Breaking Inconsistency Across Sub-Problems

For LC 56 (merge), sort by start, ties broken arbitrarily — the algorithm is correct under any tie-break. For LC 1288 (remove covered), sort by (start asc, end desc) — the tie-break is load-bearing. Always think about what happens when two intervals share a start; if your algorithm’s correctness depends on processing order, specify the tie-break explicitly.

10.8 Confusing Merge with Activity Selection

These are different problems. Merging preserves all the input’s coverage (same union). Activity selection picks a maximum subset of disjoint intervals (often less coverage than the input). If a problem says “non-overlapping” but doesn’t say “minimum cover,” ask: are we keeping all input or picking the best disjoint subset?

11. Diagram — The Sweep

flowchart LR
    Sort[Sort by start time]
    Sort --> Init[merged = [first interval]]
    Init --> Loop{For each remaining interval s,e}
    Loop -- "s ≤ last.end" --> Merge[last.end = max(last.end, e)]
    Loop -- "s > last.end" --> New[append [s,e] to merged]
    Merge --> Loop
    New --> Loop
    Loop -- done --> Out[Return merged]

What this diagram shows. The sweep maintains a single running interval (the last entry in merged). For each new interval, we ask: does it overlap-or-touch the running one? If yes, extend the running end (taking the max — never shrink). If no, the running interval is finalized; start a new running one. The decision is purely local — the greedy never needs to look more than one step back, because the sort guarantees that everything we’ve already merged is to the left of the current position. The output is the minimum-cardinality non-overlapping cover, achieved in a single linear sweep after the sort.

12. Open Questions

• Is there an o(n log n) algorithm for merge intervals? In the comparison model, no — sorting is Ω(n log n) and the lower bound applies. With non-comparison tools (e.g., integer endpoints with bounded range, suggesting Counting Sort or Radix Sort), O(n + max_endpoint) is achievable, which can be linear if endpoints are bounded.
• How does interval merging extend to higher dimensions? The merging of axis-aligned rectangles is doable in O(n log n) via sweep-line; the merging of arbitrary polygons is much harder (general boolean operations on polygons). The 1-D case is the easy base case.
• What if intervals are streamed, not all known in advance? The online version (intervals arrive one at a time, must commit to merged output without seeing future intervals) is harder — the optimum may require waiting to see whether a later interval extends the current run. With balanced-BST-based interval trees, online merging is O(log n) per insert; that’s the data-structure shift away from a simple greedy sweep.

13. See Also

• Activity Selection — sister interval-greedy with sort-by-end, not sort-by-start
• Greedy Algorithms — Proof Techniques — meta-note on exchange/stays-ahead proofs
• Two Pointers — used for LC 986 (interval list intersections)
• Sliding Window — adjacent technique for stream/window problems
• Binary Heap — used in LC 253 min-heap solution
• Sweep Line — generalization to event-driven processing (no atomic note yet)
• Big-O Notation
• SWE Interview Preparation MOC