TIP102 Unit1 Merge Intervals - codepath/compsci_guides GitHub Wiki

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.

  • Q: What is the input to the function?

    • A: The input is an array of intervals, where each interval is represented as [starti, endi].

  • Q: What is the expected output of the function?

    • A: The function should return an array of merged intervals, where all overlapping intervals have been merged into a single interval.

  • Q: How should intervals be merged?

    • A: Intervals that overlap should be merged into one interval that starts at the minimum of the starting points and ends at the maximum of the ending points.

  • Q: What should the function return if the input array is empty?

    • A: If the input array is empty, the function should return an empty array.

  • 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](/codepath/compsci_guides/wiki/1,-3],-[2,-6],-[8,-10],-[15,-18)
Expected Output: [1, 6], [8, 10], [15, 18](/codepath/compsci_guides/wiki/1,-6],-[8,-10],-[15,-18)

EDGE CASE
Input: [1, 4], [4, 5](/codepath/compsci_guides/wiki/1,-4],-[4,-5)
Expected Output: [1, 5](/codepath/compsci_guides/wiki/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