TIP102 Unit1 Merge Intervals

TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Sorting, Interval Merging

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• The function merge_intervals() should take a list of intervals and return a new list where all overlapping intervals are merged. Overlapping intervals are defined as intervals where one interval starts before another ends.

HAPPY CASE
Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
Expected Output: [[1, 6], [8, 10], [15, 18]]

EDGE CASE
Input: [[1, 4], [4, 5]]
Expected Output: [[1, 5]]

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the intervals by their starting points, then iterate through them to merge overlapping intervals.

1. If the intervals list is empty, return an empty list.
2. Sort the intervals based on the starting point using a lambda function.
3. Initialize a list `merged` and add the first interval.
4. For each subsequent interval:
   a. Compare the current interval with the last merged interval.
   b. If they overlap (i.e., the start of the current interval is less than or equal to the end of the last merged interval):
      - Merge them by updating the end of the last merged interval.
   c. If they do not overlap:
      - Append the current interval to the `merged` list.
5. Return the `merged` list.

⚠️ Common Mistakes

• Forgetting to check if the intervals list is empty at the start.
• Not handling the case where intervals just touch (e.g., [1,4] and [4,5]).

I-mplement

Implement the code to solve the algorithm.

def merge_intervals(intervals):
    if not intervals:
        return []
    
    # Sort intervals by the starting point
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:  # Overlapping intervals
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    
    return merged