Merge Intervals

Problem Statement #

Given a collection of intervals, merge all overlapping intervals and return an array of the merged intervals.

Examples #

Example 1:

Input:  [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Intervals [1,3] and [2,6] overlap, so they merge into [1,6]

Example 2:

Input:  [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping since they touch at point 4

Approach and Algorithm #

The key insight to solving this problem efficiently is to first sort the intervals by their starting points. Once sorted, we can process the intervals in a single pass and determine which ones need to be merged.

Core Algorithm Logic #

After sorting the intervals by their start times, we track three essential pieces of information:

  1. Start of current merged interval: The beginning point of the interval we’re currently building
  2. Maximum end point seen: The furthest endpoint we’ve encountered in the current merged interval
  3. Result array: Where we store all completed merged intervals

As we iterate through each interval, we need to make a decision:

If the current interval overlaps with our tracking interval:

  • The current interval’s start is less than or equal to our tracked maximum endpoint
  • We expand our tracked interval by updating the maximum endpoint if the current interval extends further
  • We continue without saving anything to the result yet

If the current interval does NOT overlap:

  • The current interval’s start is greater than our tracked maximum endpoint
  • We save the completed merged interval to our result array
  • We reset our tracking variables to start building a new merged interval

Why Sorting is Necessary #

Without sorting, we would need to compare every interval with every other interval, resulting in O(n²) time complexity. By sorting first, we guarantee that once we’ve moved past an interval, we never need to look back at it again. This reduces our comparison logic to a simple linear scan.

Implementation #

Step 1: Sort Intervals by Start Time #

// Comparison function for sorting intervals by their start point
const sortByStart = (a, b) => {
    if (a[0] < b[0]) {
        return -1;
    }
    else if (a[0] > b[0]) {
        return 1;
    }
    return 0;
};

intervals = intervals.sort(sortByStart);

Step 2: Main Merge Logic #

var merge = function(intervals) {
    // Handle edge case: empty input
    if (intervals.length === 0) {
        return [];
    }
    
    // Sort intervals by start time
    const sortByStart = (a, b) => {
        if (a[0] < b[0]) {
            return -1;
        }
        else if (a[0] > b[0]) {
            return 1;
        }
        return 0;
    };
    intervals = intervals.sort(sortByStart);
    
    // Initialize tracking variables with the first interval
    let start = intervals[0][0];
    let max = intervals[0][1];
    let result = [];
    
    // Process each interval
    for (let i = 0; i < intervals.length; i++) {
        let cur = intervals[i];
        
        if (max >= cur[0]) {
            // Current interval overlaps with our tracked interval
            // Expand the merged interval if necessary
            max = Math.max(cur[1], max);
        }
        else {
            // Current interval does not overlap
            // Save the completed merged interval
            result.push([start, max]);
            
            // Start tracking a new interval
            start = cur[0];
            max = cur[1];
        }
    }
    
    // Don't forget to save the last merged interval
    result.push([start, max]);
    
    return result;
};

Complexity Analysis #

Time Complexity: O(n log n) #

The algorithm consists of two main operations:

  1. Sorting: O(n log n) - We sort all n intervals by their start time
  2. Linear scan: O(n) - We iterate through the sorted intervals once

Since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity: O(1) or O(n) #

The space complexity depends on how we count it:

  • O(1) auxiliary space: We only use three tracking variables (start, max, result), which don’t scale with input size
  • O(n) total space: The result array could potentially contain all n intervals if none overlap

In algorithm analysis, we typically refer to the auxiliary space (excluding the output), so we consider this O(1) auxiliary space complexity.

However, we should note that most sorting algorithms use O(log n) space for their call stack, so technically the space complexity is O(log n) when accounting for the sorting operation.

Visual Walkthrough #

Let’s trace through Example 1 step by step:

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

After sorting: [[1,3],[2,6],[8,10],[15,18]] (already sorted)

Initial state:
  start = 1, max = 3, result = []

i=0: [1,3]
  max (3) >= cur[0] (1) → overlapping
  max = max(3, 3) = 3
  
i=1: [2,6]
  max (3) >= cur[0] (2) → overlapping
  max = max(3, 6) = 6
  
i=2: [8,10]
  max (6) < cur[0] (8) → NOT overlapping
  Push [1,6] to result
  start = 8, max = 10
  
i=3: [15,18]
  max (10) < cur[0] (15) → NOT overlapping
  Push [8,10] to result
  start = 15, max = 18

After loop: Push [15,18] to result

Final result: [[1,6],[8,10],[15,18]]

Edge Cases to Consider #

  1. Empty array: Return empty array
  2. Single interval: Return the interval as-is
  3. No overlaps: Return all intervals unchanged
  4. All intervals overlap: Return a single merged interval
  5. Intervals that touch at endpoints: Should be merged (e.g., [1,4] and [4,5])
  6. Completely contained intervals: Inner interval disappears (e.g., [1,10] and [2,5] → [1,10])

Optimization Notes #

  • The sorting step is the bottleneck of this algorithm
  • If intervals are already sorted or nearly sorted, we could use a more efficient sorting algorithm like insertion sort
  • If we’re allowed to modify the input array, we can sort in-place to save space
  • For online scenarios where intervals arrive one at a time, we might use a different data structure like a balanced BST or interval tree
  • Insert Interval
  • Employee Free Time
  • Meeting Rooms II
  • Non-overlapping Intervals

Conclusion #

The merge intervals problem is a classic example of how proper sorting can simplify an otherwise complex problem. By ensuring intervals are sorted by start time, we reduce the problem to a straightforward single-pass algorithm that efficiently identifies and merges overlapping intervals. This pattern appears frequently in scheduling, calendar, and time-based problems.

Previous Jump Game: A Deep Dive into Algorithmic Solutions Odd Even Linked List Next