Merge Intervals
MedPrompt
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the problem as finding connected components in a graph. Each interval is represented as a node, and an edge connects two nodes if their corresponding intervals overlap. The core idea is that all intervals that can be merged together form a single connected component in this graph. By finding these components, we can merge all intervals within each one to get the final result.
Algorithm
- Build a graph where each interval is a node.
- Add an edge between two nodes if their intervals overlap. This requires comparing every pair of intervals, taking O(N²) time.
- Initialize a
visitedarray and a result list. - Iterate through each interval (node). If a node hasn't been visited, it's part of a new connected component.
- Start a graph traversal (like DFS or BFS) from this unvisited node to find all intervals in the component.
- During the traversal, keep track of the minimum start and maximum end of all intervals in the current component.
- Once the traversal for a component is complete, add the merged interval
[min_start, max_end]to the result list. - Repeat until all nodes are visited.
Walkthrough
The algorithm proceeds in two main phases: graph construction and component merging.
-
Graph Construction: We first build an undirected graph. We iterate through every possible pair of intervals. For each pair, we check if they overlap. An overlap occurs if
interval1.start <= interval2.endandinterval2.start <= interval1.end. If they do, we add an edge between the nodes representing these two intervals. This process takes O(N²) time as it involves a nested loop over the N intervals. -
Component Merging: After building the graph, we traverse it to find its connected components. We can use Depth-First Search (DFS) or Breadth-First Search (BFS). We maintain a
visitedarray to keep track of nodes we've already processed. We iterate through all nodes from 0 to N-1. If a node hasn't been visited, we start a traversal from it. This traversal will find all nodes (intervals) in one connected component. For each component, we find the minimum start time and the maximum end time among all its intervals. This[min_start, max_end]pair forms a single merged interval. We add this to our result list and continue until all nodes have been visited.
import java.util.*; class Solution { public int[][] merge(int[][] intervals) { if (intervals.length <= 1) { return intervals; } int n = intervals.length; Map<Integer, List<Integer>> graph = new HashMap<>(); for (int i = 0; i < n; i++) { graph.put(i, new ArrayList<>()); } // Build the graph by connecting overlapping intervals for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (overlaps(intervals[i], intervals[j])) { graph.get(i).add(j); graph.get(j).add(i); } } } List<int[]> merged = new ArrayList<>(); boolean[] visited = new boolean[n]; // Find connected components and merge them for (int i = 0; i < n; i++) { if (!visited[i]) { List<Integer> componentNodes = new ArrayList<>(); Stack<Integer> stack = new Stack<>(); stack.push(i); visited[i] = true; // DFS to find all nodes in the component while (!stack.isEmpty()) { int node = stack.pop(); componentNodes.add(node); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; stack.push(neighbor); } } } // Merge all intervals in the found component merged.add(mergeComponent(componentNodes, intervals)); } } return merged.toArray(new int[merged.size()][]); } private boolean overlaps(int[] a, int[] b) { return a[0] <= b[1] && b[0] <= a[1]; } private int[] mergeComponent(List<Integer> componentNodes, int[][] intervals) { int minStart = Integer.MAX_VALUE; int maxEnd = Integer.MIN_VALUE; for (int i : componentNodes) { minStart = Math.min(minStart, intervals[i][0]); maxEnd = Math.max(maxEnd, intervals[i][1]); } return new int[]{minStart, maxEnd}; }}Complexity
Time
O(N²)
Space
O(N²)
Trade-offs
Pros
Conceptually demonstrates the connectivity aspect of the problem.
Cons
Highly inefficient with a time complexity of O(N²).
Requires O(N²) space in the worst case to store the graph.
More complex to implement compared to the sorting approach.
The most efficient way to solve this problem is by first sorting the intervals based on their start times. Once sorted, we can iterate through the intervals and merge them in a single pass. If the current interval overlaps with the previous merged interval, we combine them. Otherwise, we add the current interval as a new, separate interval to our result.
Algorithm
- If the input array has fewer than two intervals, return the original array as no merging is possible.
- Sort the intervals based on their start times in ascending order.
- Initialize a list,
merged, to store the result. Add the first interval from the sorted array tomerged. - Iterate through the sorted intervals from the second interval onwards.
- For each
currentinterval, compare it with thelastinterval in themergedlist. - If the
currentinterval overlaps with thelastinterval (i.e.,current[0] <= last[1]), merge them by updating the end of thelastinterval tomax(last[1], current[1]). - If they do not overlap, add the
currentinterval to themergedlist. - After the loop, convert the
mergedlist back to a 2D array and return it.
Walkthrough
The intuition behind this approach is that by sorting the intervals by their start points, we can guarantee that when we consider a new interval i, it will either overlap with the most recently added interval in our merged list or it won't overlap with any interval in the merged list. This simplifies the merging logic significantly.
The algorithm is as follows:
- Sort the input
intervalsarray based on the start value of each interval. - Create a new list,
merged, to store the final non-overlapping intervals. Add the very first interval from the sorted list tomerged. - Iterate through the rest of the sorted intervals, starting from the second one.
- For each
currentInterval, look at thelastIntervalin themergedlist. - If
currentInterval.startis less than or equal tolastInterval.end, it means there is an overlap. We then updatelastInterval.endto be the maximum of its current end andcurrentInterval.end. This effectively merges the two intervals. - If there is no overlap (
currentInterval.start > lastInterval.end), it means thecurrentIntervalstarts after thelastIntervalends, so they are distinct. We add thecurrentIntervalas a new entry to ourmergedlist. - Finally, we convert the
mergedlist back into a 2D array and return it.
import java.util.Arrays;import java.util.LinkedList;import java.util.List; class Solution { public int[][] merge(int[][] intervals) { if (intervals.length <= 1) { return intervals; } // Sort intervals based on the start time Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); LinkedList<int[]> merged = new LinkedList<>(); for (int[] interval : intervals) { // if the list of merged intervals is empty or if the current // interval does not overlap with the previous, simply append it. if (merged.isEmpty() || merged.getLast()[1] < interval[0]) { merged.add(interval); } // otherwise, there is overlap, so we merge the current and previous // intervals by updating the end of the last interval. else { merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]); } } return merged.toArray(new int[merged.size()][]); }}Complexity
Time
O(N log N)
Space
O(N)
Trade-offs
Pros
Very efficient with a time complexity of O(N log N), dominated by the sort.
Space efficient, using O(N) space for the result (or O(log N) for sorting stack space).
The logic is clean, simple, and easy to implement correctly.
Cons
The primary cost is the initial sort. If the intervals were already sorted, the complexity would be O(N).
Solutions
Solution
public class Solution { public int[][] Merge(int[][] intervals) { intervals = intervals.OrderBy(a => a[0]).ToArray(); var ans = new List < int[] > (); ans.Add(intervals[0]); for (int i = 1; i < intervals.Length; ++i) { if (ans[ans.Count - 1][1] < intervals[i][0]) { ans.Add(intervals[i]); } else { ans[ans.Count - 1][1] = Math.Max(ans[ans.Count - 1][1], intervals[i][1]); } } return ans.ToArray(); }}class Solution {public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b)->a[0] - b[0]); List<int[]> ans = new ArrayList<>(); ans.add(intervals[0]); for (int i = 1; i < intervals.length; ++i) { int s = intervals[i][0], e = intervals[i][1]; if (ans.get(ans.size() - 1)[1] < s) { ans.add(intervals[i]); } else { ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], e); } } return ans.toArray(new int[ans.size()][]); }}/** * @param {number[][]} intervals * @return {number[][]} */ var merge = function ( intervals ) { intervals . sort (( a , b ) => a [ 0 ] - b [ 0 ]); const result = []; const n = intervals . length ; let i = 0 ; while ( i < n ) { const left = intervals [ i ][ 0 ]; let right = intervals [ i ][ 1 ]; while ( true ) { i ++ ; if ( i < n && right >= intervals [ i ][ 0 ]) { right = Math . max ( right , intervals [ i ][ 1 ]); } else { result . push ([ left , right ]); break ; } } } return result ; };class Solution {public: vector<vector<int>> merge(vector<vector<int>> &intervals) { sort(intervals.begin(), intervals.end()); vector<vector<int>> ans; ans.emplace_back(intervals[0]); for (int i = 1; i < intervals.size(); ++i) { if (ans.back()[1] < intervals[i][0]) { ans.emplace_back(intervals[i]); } else { ans.back()[1] = max(ans.back()[1], intervals[i][1]); } } return ans; }};# Definition for an interval. # class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e class Solution ( object ): def merge ( self , intervals ): """ :type intervals: List[Interval] :rtype: List[Interval] """ ans = [] for intv in sorted ( intervals , key = lambda x : x . start ): if ans and ans [ - 1 ]. end >= intv . start : ans [ - 1 ]. end = max ( ans [ - 1 ]. end , intv . end ) else : ans . append ( intv ) return ans ###### ''' >>> intervals = [[111,222],[1,3],[2,6],[8,10],[15,18]] >>> intervals.sort() >>> intervals [[1, 3], [2, 6], [8, 10], [15, 18], [111, 222]] ''' class Solution : def merge ( self , intervals : List [ List [ int ]]) -> List [ List [ int ]]: intervals . sort () # default sort also ok ans = [ intervals [ 0 ]] for s , e in intervals [ 1 :]: if ans [ - 1 ][ 1 ] < s : ans . append ([ s , e ]) else : ans [ - 1 ][ 1 ] = max ( ans [ - 1 ][ 1 ], e ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.