Merge Intervals

• Difficulty: Easy
• Primary pattern: Arrays & Strings
• Tags: Array, Sorting, Quicksort
• Time taken: 05:24
• LeetCode Link

Key Idea

• Sorting the list of lists first based on start
• Use sorted list to confirm and check, if greater then we add to output list, if not it is consider same

Solution

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Understanding:
            # Merge overlapping intervals
            # Array of Start,end
        
        # Sorting based on start
        intervals.sort(key=lambda x: x[0])

        merged = []
        for start, end in intervals:
            # If merged is empty OR start is greater than last end
            # You create new entry
            if not merged or start > merged[-1][1]:
                merged.append([start,end])
            else:
                # else it is keep checking
                merged[-1][1] = max(merged[-1][1], end)
        return merged

Complexity

• Time: O(n logn)
• Space: O(n)