Leetcode 56 - Merge Intervals

Open Table of contents

Problem
Approaches
- Sorting and Merging Approach
- Connected Components Approach
Solution: Sorting and Merging
Solution: Connected Components

Problem

Given an array of intervals 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 <= 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 Depth-First Search (DFS) or Breadth-First 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]].
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]].

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 non-overlapping

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]]