56. Merge Intervals

url: https://leetcode.com/problems/merge-intervals/description/

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

💻 Code

Approach :

• There are two cases to be considered:
  1. Overlapping intervals $\rightarrow$ merge them to make a single interval
  2. No overlapping intervals $\rightarrow$ present themselves as it was
• Sort on the first element of each interval

1. Solution

• TC: $O(n \log n)$
  • sorted(): $O(n \log n)$
  • iteration: $O(n)$
• SC: $O(n)$

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # sort based on the starting point of each interval
        sorted_intervals = sorted(intervals)
        merged = []

        for interval in sorted_intervals:
            # cases: starting interval or not overlapping
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            # when overlapping, merge them!
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

There are only 2 cases to be considered, whether intervals are overlapping or not. Thus, focusing on the overlapping part is the key to solving this problem. The method checks between the ending part of the existing interval and the starting part of the incoming part.

There is another way to sort the input using lambda instead of sorted().
sorted_intervals = intervals.sort(key=lambda x: x[0])
This allows us to choose sorting intervals based on the starting position. Thus, we can use this flexibly.

2. Additional Practice

252. Meeting Rooms
253. Meeting Rooms II