Given a list of intervals, where each interval is represented as a pair of integers [start, end], write a function to merge overlapping intervals.

Two intervals [a, b] and [c, d] are considered overlapping if they intersect, i.e., b >= c. When two overlapping intervals are found, merge them into a single interval.

Function Signature:

from typing import List

def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
    """
    Merge overlapping intervals and return the merged list.

    Parameters:
    - intervals: List of intervals represented as pairs [start, end].

    Returns:
    - List[List[int]]: Merged list of intervals.
    """
    # Your code here

Example:

# Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
# Output: [[1, 6], [8, 10], [15, 18]]

# Input: [[1, 10]]
# Output: [[1, 10]]

# Input: [[1, 1], [1, 1], [1, 1]]
# Output: [[1, 1]]

Note:

  • The intervals in the input list are not necessarily sorted.
  • The input list can be empty.
  • You can assume that the input intervals are valid, where start <= end.

Instructions:

  • Write the merge_intervals function to solve the problem.
  • Implement your solution in Python.
  • Feel free to use helper functions if needed.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊