Merge Intervals Pattern: Solve Scheduling Problems with Sort and Sweep

Scenario context

Sort intervals by start time, then sweep left-to-right and merge any interval whose start ≤ the current running end. O(n log n) time, O(n) space. One pattern — three interview problems solved.

Your calendar app needs to render free time slots. You have 500 meetings stored as [start, end] pairs. Some overlap, some are back-to-back, some are completely separate. Before you can show anything useful, you need to…

This walkthrough focuses on When Two Meetings Overlap: The Scheduling Problem That Launched This Pattern.

Before making a design choice, clarify:

• Your calendar app needs to render free time slots.
• You have 500 meetings stored as [start, end] pairs.
• Some overlap, some are back-to-back, some are completely separate.

Concepts in play: jvm-internals-and-garbage-collection, quantization-and-llm-inference, core-algorithm-patterns, sorting-and-searching-algorithms

Stage 1 — The Overlap Condition: When a.end >= b.start

• Two intervals a = [a.start, a.end] and b = [b.start, b.end] (where a.start <= b.start after sorting) overlap when: If this holds, the merged interval spans [a.start, max(a.end, b.end)] .
• Note the max — b might be entirely inside a , in which case a.end stays unchanged.
• Three states exist after sorting: The touching case matters: [1, 3] and [3, 5] share the point 3 and should merge to [1, 5] .
• The condition a.end = b.start handles all three cases at once.

a.end >= b.start

Observable outcome: The condition a.end = b.start handles all three cases at once.

Stage 2 — Sort-Then-Sweep: The Two-Step Algorithm for Merging Intervals

• The algorithm fits in two clean phases: Phase 1 — Sort all intervals by their start time.
• After sorting, any potential overlap between interval i and interval j (where i < j ) only ever involves j possibly overlapping with the running merged interval — never with an earlier one you already committed.
• Phase 2 — Sweep left-to-right maintaining a current interval: - If the next interval starts before or at current.end , extend current.end to max(current.end, next.end) .
• • Otherwise commit current to the result and make next the new current .

import java.util.*;

public class MergeIntervals {

    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;

        // Phase 1: sort by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> result = new ArrayList<>();
        int[] current = intervals[0];

        // Phase 2: sweep and merge
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= current[1]) {
                // Overlapping or touching — extend the current interval
                current[1] = Math.max(current[1], intervals[i][1]);
            } else {
                // Gap found — commit current and start fresh
                result.add(current);
                current = intervals[i];
            }
        }
        result.add(current); // don't forget the last interval

        return result.toArray(new int[result.size()][]);
    }
}

Observable outcome: - Otherwise commit current to the result and make next the new current .

Stage 3 — Three Interval States: Non-Overlapping, Touching, and Overlapping

• After sorting, each interval is visited exactly once — either merged into the running window or committed to the output.
• The three concrete cases from the condition table above map directly to this flowchart's left branch (merge) and right branch (commit).
• The max on the end time handles the case where one interval is completely inside another.

flowchart TD
    A[Sort intervals by start time] --> B[Pick first as current]
    B --> C{Next interval start <= current end?}
    C -->|"Yes  overlapping or touching"| D["Extend: current.end = max(current.end, next.end)"]
    D --> E[Advance to following interval]
    E --> C
    C -->|"No  gap found"| F[Commit current to result list]
    F --> G[Set next as new current]
    G --> C
    C -->|"No more intervals"| H[Commit final current]
    H --> I[Return result list]

Observable outcome: The max on the end time handles the case where one interval is completely inside another.

Stage 4 — Real-World Uses: Google Calendar, CPU Scheduling, and Genome Assembly

• Calendar free-slot computation is the most direct use.
• Given a list of busy intervals, merge them and then take the complement of the merged spans against the total working day to find free slots.
• Google Calendar's free/busy API does exactly this at scale.
• CPU burst scheduling in operating systems uses interval merging to consolidate contiguous memory allocations or time-slice segments.

Observable outcome: CPU burst scheduling in operating systems uses interval merging to consolidate contiguous memory allocations or time-slice segments.

Stage 5 — When Merge Intervals Breaks Down (and What to Use Instead)

• The sort-then-sweep approach has specific failure modes to watch for: Edge case — single-point intervals : [3, 3] is a zero-length interval that can still merge with [2, 3] or [3, 5] .
• The condition a.end = b.start handles this correctly — confirm your implementation does not use strict greater-than.
• Edge case — containment : [1, 10] completely contains [3, 6] .
• The max(current.end, next.end) step handles this, but if you naively take next.end instead of max , you silently shrink the merged interval.

Observable outcome: The max(current.end, next.end) step handles this, but if you naively take next.end instead of max , you silently shrink the merged interval.

Stage 6 — Choosing Between Interval Merge, Sweep Line, and Interval Trees

• The sort-then-sweep pattern is the right choice whenever you process a static batch of intervals and need the merged result.
• Dynamic scenarios call for interval trees.

Observable outcome: Dynamic scenarios call for interval trees.

End-to-end outcome

After working through the stages, you should be able to explain:

• • Sort by start time — this converts a 2D overlap check into a 1D greedy sweep.
• • Overlap condition : next.start <= current.end — use <= to handle touching intervals.

Alternatives considered

The source focuses on one primary design. A second architecture is not compared, so no alternative is invented here.

Failure and degraded modes

The source does not isolate a separate failure mode. Limits that matter for the scenario are called out in the stage decisions above.