Merge Intervals | Leetcode 56 | Brute Force and Optimal

If you want to master array problems, “Merge Intervals” is a must-know question! In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with comments, dry runs, and clear explanations.

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.

Here’s the [Problem Link] to begin with.

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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Brute Force Solution

Intuition and Approach

Let’s solve the problem step by step in the simplest way:

1. Sort the Intervals:
   Sorting helps us line up all intervals so that overlapping intervals are next to each other.
2. Check Each Interval:
   For every interval, try to merge it with all future intervals that overlap with it.
3. Skip Already Merged Intervals:
   If an interval is already covered by a previous merge, skip it.
4. Why does this work?
   We check every possible overlap and merge accordingly. This ensures all intervals are merged correctly, but it’s not the most efficient.

Code Implementation

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        intervals.sort()                         # sort intervals by start time
        ans = []
        for i in range(n):
            start, end = intervals[i][0], intervals[i][1]   # current interval

            # skip if current interval is already merged
            if len(ans) != 0 and end <= ans[-1][1]:
                continue

            # try to merge with future overlapping intervals
            for j in range(i + 1, n):
                if intervals[j][0] <= end:                # overlap found
                    end = max(end, intervals[j][1])       # extend end to the farthest overlap
                else:
                    break                                 # stop if no overlap
            ans.append([start, end])                      # add merged interval to answer
        return ans

Code Explanation

• First, we sort the intervals to make overlapping intervals adjacent.
• For each interval, we check if it’s already merged; if so, we skip it.
• Then, we look ahead to merge all intervals that overlap with the current one.
• We add the merged interval to our answer list.

Dry Run

Input:
intervals = [[1],,,]

• After sorting: [[1],,,]
• Start with . overlaps, so merge to .
• does not overlap, so add .
• does not overlap, so add .
• Final output: [[1],,]

Time and Space Complexity

• Time Complexity: O(N^2)
  For each interval, we may check all future intervals.
• Space Complexity: O(N)
  For the answer list.

Conclusion

The brute force approach is easy to understand but slow for large lists. It’s good for learning the basics of the problem.

Optimal Solution

Intuition and Approach

We can solve this problem much faster by merging intervals as we go:

1. Sort the Intervals:
   Sorting puts overlapping intervals next to each other.
2. Merge on the Go:
   As we go through each interval, check if it overlaps with the last interval in our answer list. If it does, merge them. If not, add it as a new interval.
3. Why does this work?
   After sorting, all overlaps are adjacent, so we only need to look at the last merged interval.

Code Implementation

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        intervals.sort()                              # sort intervals by start time
        ans = []
        for i in range(n):
            # if ans is empty or no overlap, add interval
            if len(ans) == 0 or intervals[i][0] > ans[-1][1]:
                ans.append(intervals[i])
            else:
                # merge with the last interval in ans
                ans[-1][1] = max(ans[-1][1], intervals[i][1])
        return ans

Code Explanation

• We sort the intervals.
• For each interval, if it doesn’t overlap with the last interval in the answer, we add it.
• If it does overlap, we merge it with the last interval by updating the end value.

Dry Run

Input:
intervals = [[1],,,]

• After sorting: [[1],,,]
• : add to answer → [[1]]
• : overlaps with , merge to  → [[1]]
• : no overlap, add → [[1],]
• : no overlap, add → [[1],,]

Time and Space Complexity

• Time Complexity: O(N log N)
  Sorting dominates; merging is O(N).
• Space Complexity: O(N)
  For the answer list.

Conclusion

The optimal solution is efficient and elegant. It’s the best approach for interviews and large datasets.

Final Thoughts

The “Merge Intervals” problem is a great example of how sorting and merging can simplify complex problems. Start with brute force to understand the basics, then use the optimal solution for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.