Merge Intervals

Learning goal: Recognize that the task is to replace many possibly overlapping ranges with the smallest equivalent set of disjoint ranges.

Core idea An interval [start, end] covers every point from start through end. If two intervals overlap, their union is another interval whose start is the earlier start and whose end is the larger end. The challenge is deciding which interval should be compared with the next one.

Algorithm plan

• Read the intervals without assuming they are ordered.
• Sort them by their start values.
• Maintain a result list whose last interval is the only one that can overlap the current interval.
• Merge when current.start <= last.end; otherwise append a new interval.

Micro-example For [1,4] and [3,6], the ranges overlap because 3 <= 4. Their union is [1,6]. For [1,4] and [8,10], there is a gap, so both remain separate.

Pitfalls

• Returning the intervals in input order instead of sorted order.
• Treating touching intervals as disjoint when the condition includes equality.
• Mutating an interval in a way that accidentally loses the original start.

Recap

• Overlapping ranges can be represented by one larger range.
• Sorting creates the order needed for a one-pass merge.
• The output contains non-overlapping intervals.

Learning goal: Explain why sorting by start time reduces a pairwise merging problem to a single sweep.

Core idea Before sorting, a later-looking interval in the input might actually begin far to the left and overlap several intervals already processed. After sorting, starts never decrease. Therefore, once the current interval starts after the end of the last merged interval, it cannot overlap any earlier result interval either. The last merged interval is the only candidate that needs comparison.

Algorithm plan

• Sort intervals using start as the primary key.
• Let merged begin with the first sorted interval.
• For each current interval:
  • If current.start <= merged[-1].end, update the end to the larger endpoint.
  • Otherwise append current as a new disjoint range.

Micro-example Sorted order: [1,4], [3,6], [5,7], [8,10]. The first three connect through overlap; [8,10] starts after the merged end 7.

Pitfalls

• Forgetting to sort first is the central correctness mistake.
• Comparing with the original previous input interval instead of merged[-1] fails after an extension.
• Using < instead of <= changes the treatment of touching intervals.

Recap

• Ordered starts let us discard old comparisons.
• The result list stores the current union of each connected group.
• Every interval is examined once after sorting.

Learning goal: Translate the interval strategy into precise implementation steps and an invariant.

Core idea The result is built incrementally. At every iteration, merged is sorted, non-overlapping, and represents exactly the union of all sorted intervals processed so far. Because the next interval starts no earlier than the previous ones, only the final interval in merged can still overlap it.

Algorithm plan

1. Sort intervals by interval[0].
2. Copy the first interval into merged.
3. For each remaining interval, read last = merged[-1].
4. If current.start <= last.end, set last.end = max(last.end, current.end).
5. Otherwise, append a copy of current.
6. Return merged.

intervals.sort(key=lambda interval: interval[0])
merged = [intervals[0][:]]
for start, end in intervals[1:]:
    if start <= merged[-1][1]:
        merged[-1][1] = max(merged[-1][1], end)
    else:
        merged.append([start, end])

Micro-example With last = [1,6] and current = [5,7], overlap holds, so the end becomes 7. With last = [1,7] and current = [8,10], there is a gap, so append.

Pitfalls

• Do not initialize from an empty input unless the implementation supports that case explicitly.
• Compare the current start with the merged end, not with the merged start.
• Use max because a contained interval must not shrink the range.

Recap

• The invariant keeps merged canonical after every iteration.
• The only updates are extending the tail or appending a new interval.
• Sorting plus sweeping is the complete algorithm.

Learning goal: Trace every decision on [[5,7],[1,4],[3,6],[8,10]] and connect it to the invariant.

Core idea The input arrives unsorted, so the first meaningful state change is sorting. We then seed merged with [1,4]. Each later interval either connects to the tail and extends its right endpoint, or begins after the tail and must be appended as a separate result interval.

Algorithm plan

• Sort the input by each interval's first value.
• Start with merged = [[1,4]].
• Process [3,6]: 3 <= 4, so extend to [1,6].
• Process [5,7]: 5 <= 6, so extend to [1,7].
• Process [8,10]: 8 > 7, so append it.

Micro-example The chain [1,4] overlaps [3,6], and [3,6] overlaps [5,7]. Even though [1,4] and [5,7] do not overlap directly, transitive connection puts all three in one merged range.

Pitfalls

• Stopping after one merge misses chains of overlapping intervals.
• Comparing [5,7] with [1,4] would incorrectly reject it.
• The final gap is detected only after the merged end is correctly extended to 7.

Recap

• Sorted order: [1,4], [3,6], [5,7], [8,10].
• First three intervals become [1,7].
• Final answer: [[1,7],[8,10]].

Learning goal: Identify the boundary conditions that distinguish a correct interval merge from a nearly correct one.

Core idea Most bugs come from using the wrong ordering or the wrong overlap boundary. Sorting must happen before the sweep, and intervals that touch should merge when the problem treats coverage as continuous. The update must preserve the farthest right endpoint seen in the current connected group.

Algorithm plan

• Sort by start, breaking ties consistently if needed.
• Treat current.start <= last.end as overlap.
• Extend with max(last.end, current.end).
• Append only when current.start > last.end.
• Handle one interval naturally: it becomes the initial result.

Micro-example [[1,2],[2,5]] merges to [[1,5]] because 2 <= 2. [[1,10],[3,4]] stays [[1,10]]; the inner interval must not shorten the end.

Pitfalls

• Sorting by end instead of start does not provide the needed sweep invariant.
• Using < rejects touching intervals.
• Appending every overlap instead of extending the tail leaves duplicates.
• Modifying the input can be surprising when callers expect it unchanged; copy intervals if necessary.

Recap

• Sort before any merge decision.
• Use <= for touching ranges.
• Extend with the maximum end and preserve the result invariant.

Learning goal: Analyze the cost of the sorted sweep and summarize the reusable interval pattern.

Core idea Sorting dominates the runtime. Once the intervals are ordered, the sweep examines each interval once and performs constant-time work per interval. The result may contain up to n intervals, so storing it requires linear additional space.

Algorithm plan

• Spend O(n log n) time to sort n intervals.
• Spend O(n) time to scan and merge them.
• Store the output in O(n) space.
• Return the canonical list of disjoint intervals.

Micro-example For n = 4, sorting establishes the order [1,4], [3,6], [5,7], [8,10]. The four-item sweep then performs three overlap decisions and produces two output intervals.

Pitfalls

• Calling the sweep O(n log n) without explaining that sorting is the dominant term.
• Claiming O(1) space while ignoring the output list.
• Replacing the sort with repeated searches, which can lose the linear sweep advantage.

Recap

• Time: O(n log n) for sorting plus O(n) for scanning.
• Space: O(n) for the merged output.
• The reusable pattern is sort by start, compare with the result tail, then extend or append.