A LeetCode Daily Series — Day 93

Today’s problem is called "Merge Intervals"

Updated: at 02:01 AM

In this article, we tackle the “Merge Intervals” problem, a common coding challenge that helps us understand how to manage overlapping intervals efficiently. Let’s dive into the problem, explore a solution, and understand the logic behind it.

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

Cover Image

Understanding the Problem

Given an array of intervals where intervals[i] = [starti, endi], our goal is to 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.

Using Efficient Approach (Sorting and Merging)

By sorting the intervals based on their starting times, we can easily identify overlapping intervals. As we iterate through the sorted intervals, we merge them when necessary. This approach ensures that we only traverse the list a couple of times, making it efficient.

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for interval in intervals:
        if merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

Explanation

  1. Sort Intervals: We sort the intervals based on the starting time using intervals.sort(key=lambda x: x[0]). This allows us to process intervals in the correct order.
  2. Initialize Merged List: We initialize the merged list with the first interval. This will store our final merged intervals.
  3. Iterate and Merge:
    • For each interval in intervals, we check if it overlaps with the last interval in merged.
    • If there is no overlap (merged[-1][1] < interval[0]), we append the current interval to merged.
    • If there is an overlap, we merge the intervals by updating the end time of the last interval in merged with the maximum end time between the overlapping intervals.
  4. Return Result: Finally, we return the merged list containing all non-overlapping intervals.

Time Complexity: The time complexity is O(n log n) due to the sorting step, where n is the number of intervals. The subsequent merging process takes O(n) time.

Space Complexity: The space complexity is O(n), as we use additional space to store the merged intervals.

Result

Conclusion

In this article, we explored an efficient method to solve the “Merge Intervals” problem using sorting and merging. This approach ensures that we handle overlapping intervals efficiently and return the desired non-overlapping intervals.

Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series