0056.Merge Intervals

• Link: 56. Merge Intervals - Medium
• Track: NeetCode150

Question

Restate the problem

• Given a list of intervals [start, end]
• Return a list of merged intervals
• Requirements:
  • If prev_end == next_start, overlap

Edge Case

• if not intervals, return []

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Sort + Merge	$O(nlogn)$	$O(n)$

Method 1 - Sort + Merge

Approach

1. Sort intervals by start time.
   • After sorting, any interval that can overlap with the current one must appear next to it (or soon after).
2. Merge using the last merged interval.
   • Keep a result list res. For each interval:
     • If it overlaps with res[-1], merge by extending the end.
     • Otherwise, start a new interval in res.

Complexity

• Time Complexity: $O(nlogn)$
  • Sort: $O(nlogn)$
  • Scan: $O(n)$
• Space Complexity: $O(n)$

Code

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        intervals.append(newInterval)
        intervals.sort(key = lambda x:x[0])
 
        merged = []        
        for start, end in intervals:
            if merged and merged[-1][1] >= start:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
 
        return merged

---

Common Mistake

• Overlap should be: start <= last_end
• Method 2: remember to sort