Intervals Pattern

The Intervals pattern handles scheduling and range overlap tasks by sorting boundary coordinates, and using sequential sweep-line scans to merge, insert, or check for conflicts.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The input is a list of pairs representing ranges (e.g. [start, end], time slots, coordinate bounds).
• The problem asks you to “merge overlapping intervals”, “find the number of meeting rooms”, or “insert a new interval”.
• The task involves resolving conflicts or scheduling timelines.

How It Works

Instead of checking all pairs of intervals (O(n²)), you sort the intervals by their start (or end) times. This reduces the problem to a linear sweep:

• Sorting: Sort intervals by start time: intervals[i][0].
• Sweep: Scan adjacent intervals:
  • If next_start <= current_end, they overlap. Merge them by setting current_end = max(current_end, next_end).
  • If next_start > current_end, they do not overlap. Add the current interval to the output and update tracking bounds.

For example, to merge [[1, 3], [2, 6], [8, 10]]:

1. The list is already sorted by start time.
2. Track: current = [1, 3].
3. Read [2, 6]: since 2 <= 3, merge: current_end = max(3, 6) = 6. current becomes [1, 6].
4. Read [8, 10]: since 8 > 6, no overlap. Output [1, 6] and set current = [8, 10].
5. Output the remaining interval [8, 10].

Complexity, With Caveats

• Time Complexity: O(n log n) where n is the number of intervals. Sorting the array dominates the execution. The sweep phase is a linear O(n) pass.
• Space Complexity: O(n) or O(log n) to store the sorted output or system sorting stack.

Minimal Code Template

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class IntervalsTemplate {
    // Merge Overlapping Intervals
    public int[][] mergeIntervals(int[][] intervals) {
        if (intervals.length <= 1) return intervals;

        // sort by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

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

        for (int i = 1; i < intervals.length; i++) {
            int[] next = intervals[i];
            if (next[0] <= current[1]) {
                // overlap: merge by updating end time
                current[1] = Math.max(current[1], next[1]);
            } else {
                // no overlap: update current to next
                current = next;
                result.add(current);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

# Merge Overlapping Intervals
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if len(intervals) <= 1:
        return intervals

    # sort by start time
    intervals.sort(key=lambda x: x[0])

    result = [intervals[0]]

    for i in range(1, len(intervals)):
        current = result[-1]
        next_interval = intervals[i]

        if next_interval[0] <= current[1]:
            # overlap: merge by updating end time
            current[1] = max(current[1], next_interval[1])
        else:
            # no overlap: append new interval
            result.append(next_interval)

    return result

#include <vector>
#include <algorithm>

class IntervalsTemplate {
public:
    // Merge Overlapping Intervals
    std::vector<std::vector<int>> mergeIntervals(std::vector<std::vector<int>>& intervals) {
        if (intervals.size() <= 1) return intervals;

        // sort by start time
        std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0];
        });

        std::vector<std::vector<int>> result;
        result.push_back(intervals[0]);

        for (size_t i = 1; i < intervals.size(); i++) {
            auto& current = result.back();
            const auto& next = intervals[i];

            if (next[0] <= current[1]) {
                // overlap: merge by updating end time
                current[1] = std::max(current[1], next[1]);
            } else {
                // no overlap: append new interval
                result.push_back(next);
            }
        }
        return result;
    }
};

Where This Pattern Falls Short

• Unsorted dynamic updates: If intervals are arriving dynamically one by one, sorting the entire list on each new entry takes O(n log n) time, which is too slow. You must use balanced binary search trees or segment trees to insert intervals in O(log n) time.
• Multidimensional intervals: If intervals are 2D (like boxes with height and width), simple 1D sorting is insufficient, and you must use spatial indexes or interval trees.

Related Patterns, Compared

• Greedy: choose this instead when scheduling non-overlapping intervals (maximize kept, minimize removed) where you sort by end times.
• Two Pointers: choose this instead when the intervals are split into two separate lists and you need to find intersections.

Frequently Asked Questions

Why do we sort by start times for merging, but end times for scheduling? We sort by start times for merging because we want adjacent intervals in sorted order to touch immediately. We sort by end times for scheduling (e.g. Non-overlapping Intervals) because choosing the interval that finishes earliest leaves the maximum space for future intervals.

How do you handle touch-point boundaries? If intervals [1, 2] and [2, 3] touch, the problem must specify whether they overlap. In LeetCode, boundary touching is usually considered overlapping for merging, but non-overlapping for schedule conflicts.

What does this pattern test in interviews? It tests your ability to handle range overlaps, coordinate array comparisons, and apply custom sorting logic.