Merge Intervals — Problem Statement & Solution Guide

ArraysMediumMixed

TimeO(n log n)

SpaceO(1) auxiliary (excluding output list)

Problem Description

You are provided with a collection of time slots, where each slot is defined by a start and an end point. Two slots are considered overlapping if they share any common time, including cases where one ends exactly when the other begins. Your task is to consolidate these slots into a minimal set of non-overlapping intervals such that the union of the resulting intervals is identical to the union of the original input intervals.

Return the merged intervals in ascending order of their start times. If the input array is empty, return an empty array. The solution must efficiently handle large datasets by ensuring that the merging process does not result in redundant checks or excessive memory usage.

DSA Pattern Breakdown

"Merge Intervals"

medium

WHY DOES IT MATTER?

The merge‑interval pattern teaches how to convert overlapping ranges into a canonical representation, a skill essential for calendar apps, memory allocators, and network firewall rule consolidation where redundancy must be eliminated.

OPTIMIZATION CHALLENGE

The key insight is that sorting imposes a linear order that collapses the O(n^2) pairwise comparison problem into a single sweep, reducing time complexity from quadratic to O(n log n) while using only O(1) extra space beyond the output list.

REAL-WORLD CONNECTION

Think of a highway toll system where each vehicle's entry and exit timestamps form intervals; merging them yields the total time the highway was occupied, analogous to aggregating log windows in distributed tracing.

During an interview, sort the intervals first, then use a mutable 'current' interval; always compare the next interval's start with the current end—if start <= end, merge by extending the end, otherwise push the current interval to the result and reset.

COMPLEXITY AT A GLANCE

⏱ Time:O(n log n)

💾 Space:O(1) auxiliary (excluding output list)

Core Theory — Why This Approach?

Merging intervals is a classic example of the greedy paradigm applied to a sorted structure. By first sorting the intervals by their start times, we guarantee that any potential overlap can only occur with the immediately preceding interval in the sorted order, allowing us to make a locally optimal decision—either extend the current merged interval or start a new one—without revisiting earlier elements. This greedy choice is provably optimal because the sorted order imposes a total order on the start points, and any solution that does not merge overlapping intervals when possible would create unnecessary fragmentation, contradicting the minimality requirement.

A naive solution might compare each interval with every other interval, leading to O(n^2) time complexity, which quickly becomes infeasible for large datasets (e.g., millions of time slots in calendar applications). The optimal approach leverages sorting (O(n log n)) followed by a single linear scan (O(n)), achieving O(n log n) overall. This reduction is crucial for real‑time systems where latency and memory footprints must stay low, and it exemplifies how ordering data can transform a combinatorial problem into a tractable one.

The underlying theory also connects to interval graphs, where each interval is a vertex and edges represent overlaps. Merging intervals corresponds to finding the minimal set of cliques that cover the graph, which in one dimension reduces to the greedy sweep line algorithm. Understanding this relationship helps engineers recognize when similar sweep‑line techniques can be applied to other problems such as skyline silhouettes, meeting room scheduling, or range query optimizations.

Interview Questions on This Problem

Q1How would you modify the merge intervals algorithm to handle a stream of intervals arriving in real time, ensuring O(log n) insertion time?

Maintain a balanced binary search tree (e.g., TreeMap) keyed by interval start. For each incoming interval, locate the predecessor and successor intervals in O(log n), check for overlap, merge as needed, and update the tree. This keeps the set of merged intervals sorted and allows O(log n) updates while preserving O(k) space where k is the current number of merged intervals.

Q2Explain why sorting by start time is sufficient; would sorting by end time ever be advantageous?

Sorting by start time ensures that any interval that could overlap with the current one appears consecutively, enabling a single pass merge. Sorting by end time does not guarantee this property because an interval with a later start but earlier end could be missed, leading to incorrect merges. However, if the problem required counting maximum non‑overlapping intervals (activity selection), sorting by end time becomes the optimal greedy strategy.

Q3In a distributed system where intervals are sharded across nodes, how can you compute the global merged intervals efficiently?

First, each node locally merges its intervals. Then, nodes exchange boundary intervals (the last interval of one node and the first of the next) to resolve cross‑node overlaps. A final pass merges these boundary intervals, yielding the global merged set with communication proportional to the number of shards, not the total interval count.

Examples

Example 1

Input

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

Output

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

Explanation: First, sort the intervals by their start times: [[1, 3], [2, 6], [8, 10], [15, 18]]. Initialize the result with the first interval [1, 3]. Compare the next interval [2, 6] with the last in the result [1, 3]. Since 2 <= 3, they overlap. Merge them by updating the end time to max(3, 6) = 6, resulting in [1, 6]. The next interval [8, 10] has a start time 8 which is greater than the current end 6, so no overlap. Append [8, 10] to the result. The final interval [15, 18] has a start time 15 > 10, so append it. The final merged list is [[1, 6], [8, 10], [15, 18]].

Example 2

Input

intervals = [[1, 4], [4, 5]]

Output

[[1, 5]]

Explanation: Sort the intervals: [[1, 4], [4, 5]]. Start with [1, 4]. The next interval [4, 5] has a start time 4 which is less than or equal to the current end 4. This indicates an overlap (touching intervals are merged). Update the end time to max(4, 5) = 5. The result becomes [[1, 5]]. No more intervals to process.

Example 3

Input

intervals = [[5, 6], [1, 2]]

Output

[[1, 2], [5, 6]]

Explanation: The input is not sorted. First, sort by start time: [[1, 2], [5, 6]]. Initialize result with [1, 2]. The next interval [5, 6] has a start time 5 which is greater than the current end 2. No overlap. Append [5, 6]. The final result is [[1, 2], [5, 6]].

Example 4

Input

intervals = [[1, 10], [2, 3], [4, 5]]

Output

[[1, 10]]

Explanation: Sort the intervals: [[1, 10], [2, 3], [4, 5]]. Start with [1, 10]. The next interval [2, 3] has start 2 <= 10, so merge. End becomes max(10, 3) = 10. Result is [[1, 10]]. The next interval [4, 5] has start 4 <= 10, so merge. End becomes max(10, 5) = 10. Result remains [[1, 10]]. All intervals are contained within the first one.

Constraints

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i <= end_i <= 10^4

Optimal Approach & Strategy

Sort intervals by start time and perform a single linear scan, merging overlapping intervals on the fly.

Brute Force Approach

Compare every interval with every other interval, merging any that overlap, and repeat until no more merges are possible.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n log n)

function mergeIntervals(intervals) { 
       if (intervals.length === 0) { 
           return []; 
       } 
       intervals.sort((a, b) => a[0] - b[0]); 
       let result = [intervals[0]]; 
       for (let i = 1; i < intervals.length; i++) { 
           if (intervals[i][0] <= result[result.length - 1][1]) { 
               result[result.length - 1][1] = Math.max(result[result.length - 1][1], intervals[i][1]); 
           } else { 
               result.push(intervals[i]); 
           } 
       } 
       return result; 
   }

class Solution { 
   public: 
       vector<vector<int>> merge(vector<vector<int>>& intervals) { 
           if (intervals.empty()) { 
               return {}; 
           } 
           sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { 
               return a[0] < b[0]; 
           }); 
           vector<vector<int>> result; 
           result.push_back(intervals[0]); 
           for (int i = 1; i < intervals.size(); i++) { 
               if (intervals[i][0] <= result.back()[1]) { 
                   result.back()[1] = max(result.back()[1], intervals[i][1]); 
               } else { 
                   result.push_back(intervals[i]); 
               } 
           } 
           return result; 
       } 
   };

import java.util.Arrays; 
   public class Solution { 
       public int[][] merge(int[][] intervals) { 
           if (intervals.length == 0) { 
               return new int[][]{}; 
           } 
           Arrays.sort(intervals, (a, b) -> a[0] - b[0]); 
           int[][] result = new int[intervals.length][]; 
           int index = 0; 
           result[index++] = intervals[0]; 
           for (int i = 1; i < intervals.length; i++) { 
               if (intervals[i][0] <= result[index - 1][1]) { 
                   result[index - 1][1] = Math.max(result[index - 1][1], intervals[i][1]); 
               } else { 
                   result[index++] = intervals[i]; 
               } 
           } 
           return Arrays.copyOf(result, index); 
       } 
   }

def merge_intervals(intervals): 
       if not intervals: 
           return [] 
       intervals.sort(key=lambda x: x[0]) 
       result = [intervals[0]] 
       for i in range(1, len(intervals)): 
           if intervals[i][0] <= result[-1][1]: 
               result[-1][1] = max(result[-1][1], intervals[i][1]) 
           else: 
               result.append(intervals[i]) 
       return result

function mergeIntervals(intervals) { 
       if (intervals.length === 0) { 
           return []; 
       } 
       intervals.sort((a, b) => a[0] - b[0]); 
       let result = [intervals[0]]; 
       for (let i = 1; i < intervals.length; i++) { 
           if (intervals[i][0] <= result[result.length - 1][1]) { 
               result[result.length - 1][1] = Math.max(result[result.length - 1][1], intervals[i][1]); 
           } else { 
               result.push(intervals[i]); 
           } 
       } 
       return result; 
   }

Asked in Top Tech Interviews

arrayssortingintervals

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Merge Intervals Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Merge Intervals — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor