Table of contents
Open Table of contents
Problem
Given an array of intervals intervals
where intervals[i] = [starti, endi]
, merge all overlapping intervals and return an array of the nonoverlapping 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 <= 10^4
intervals[i].length == 2
0 <= starti, endi <= 10^4
Approaches
The goal is to merge overlapping intervals and return the merged intervals. This problem can be efficiently solved by sorting the intervals based on their starting points.
Sorting and Merging Approach
 Sort the Intervals: Sort the intervals by their start times.
 Initialize the First Interval: Add the first interval to the result.
 Iterate and Merge: For each interval, compare it with the last interval in the result. If they overlap, merge them; otherwise, add the interval to the result.
Connected Components Approach
 Build a Graph: Create a graph where each interval is a node. Two nodes are connected if their intervals overlap.
 Find Connected Components: Use DepthFirst Search (DFS) or BreadthFirst Search (BFS) to find all connected components in the graph.
 Merge Each Component: For each connected component, merge all intervals into a single interval by taking the minimum start time and the maximum end time of all intervals in the component.
 Return Merged Intervals: The merged intervals from each connected component are the final result.
Solution: Sorting and Merging
class Solution:
def merge(self, intervals: List[List[int]]) > List[List[int]]:
if not intervals:
return []
# Sort intervals based on start time
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
prev = merged[1]
# Check if the current interval overlaps with the last interval in merged
if current[0] <= prev[1]:
# Merge the intervals
merged[1] = [prev[0], max(prev[1], current[1])]
else:
# Add the current interval to merged
merged.append(current)
return merged
Time and Memory Complexity
The time complexity is O(N log N) due to the sorting of intervals, where N is the number of intervals. The merging process is O(N), leading to a total time complexity of O(N log N). The space complexity is O(N) for the output list.
Explanation
After sorting the intervals, the algorithm checks each interval to see if it overlaps with the last interval in the merged
list. If they overlap, the intervals are merged; otherwise, the current interval is added as a new entry in merged
.
Visual Representation
Consider the input intervals = [[1,3],[2,6],[8,10],[15,18]]
.

Sorting Intervals:
 Sorted intervals:
[[1,3], [2,6], [8,10], [15,18]]
.
 Sorted intervals:

Merging Overlapping Intervals:
 Start with
[1,3]
.  Merge
[1,3]
and[2,6]
into[1,6]
. [8,10]
and[15,18]
are added as they don’t overlap with[1,6]
. Result:
[[1,6], [8,10], [15,18]]
.
 Start with
Intervals: [[1,3], [2,6], [8,10], [15,18]]
Step 1: Sort intervals
Step 2: Merge [1,3] and [2,6] into [1,6]
Step 3: Add [8,10] and [15,18] as nonoverlapping
Result: [[1,6], [8,10], [15,18]]
Solution: Connected Components
class Solution:
def merge(self, intervals: List[List[int]]) > List[List[int]]:
if not intervals:
return []
def overlap(a, b):
""" Check if two intervals a and b overlap """
return a[1] >= b[0] and b[1] >= a[0]
def merge_intervals(component):
""" Merge all intervals in a connected component """
min_start = min(interval[0] for interval in component)
max_end = max(interval[1] for interval in component)
return [min_start, max_end]
# Build the graph
graph = collections.defaultdict(list)
for i, interval1 in enumerate(intervals):
for j in range(i + 1, len(intervals)):
interval2 = intervals[j]
if overlap(interval1, interval2):
graph[tuple(interval1)].append(interval2)
graph[tuple(interval2)].append(interval1)
# Find connected components
visited = set()
components = []
for interval in intervals:
if tuple(interval) not in visited:
stack = [interval]
component = []
while stack:
node = stack.pop()
if tuple(node) not in visited:
visited.add(tuple(node))
component.append(node)
for neighbor in graph[tuple(node)]:
if tuple(neighbor) not in visited:
stack.append(neighbor)
components.append(component)
# Merge each connected component
return [merge_intervals(component) for component in components]
Time and Memory Complexity
The time complexity of building the graph is O(N^2), where N is the number of intervals, as we compare each interval with every other interval. The DFS or BFS for finding connected components also takes O(N^2) in the worst case. Hence, the overall time complexity is O(N^2). The space complexity is O(N) for storing the graph and connected components.
Explanation
This solution first constructs a graph where each node represents an interval, and edges represent overlaps between intervals. Then, it uses DFS or BFS to find all connected components, which are groups of overlapping intervals. Finally, it merges all intervals within each connected component into a single interval.
Visual Representation
To provide a clearer visual representation for the Connected Components Approach to LeetCode problem 56  “Merge Intervals”, let’s break down the process with a detailed example and illustrate how the intervals are merged based on their connectivity.
Visual Representation of the Connected Components Approach
Consider the input intervals = [[1,3],[2,6],[8,10],[15,18]]
.
Step 1: Building the Graph
 Nodes are the intervals themselves:
[[1,3], [2,6], [8,10], [15,18]]
.  Edges are drawn between intervals that overlap. In this case, an edge between
[1,3]
and[2,6]
.
Graph Representation:
[1,3]
/
[2,6] [8,10] [15,18]
Step 2: Finding Connected Components
 Identify components by traversing the graph. Each connected set of nodes forms a component.
 Component 1:
[1,3]
and[2,6]
are connected.  Component 2:
[8,10]
is standalone.  Component 3:
[15,18]
is standalone.
Connected Components:
 Component 1: [[1,3], [2,6]]
 Component 2: [[8,10]]
 Component 3: [[15,18]]
Step 3: Merging Components
 Merge intervals in each component.
 Component 1:
[1,3]
and[2,6]
merge into[1,6]
.  Component 2 and 3 remain the same as they are standalone.
Merging Components:
 Component 1: [1,6]
 Component 2: [8,10]
 Component 3: [15,18]
Final Result
 The merged intervals are
[[1,6], [8,10], [15,18]]
.
Final Merged Intervals: [[1,6], [8,10], [15,18]]