Solution for interview question: Merge Intervals

1. Understanding the Problem

Given an array of intervals where each interval is represented as [start, end], merge overlapping intervals.
The goal is to return a list of non-overlapping intervals that cover all intervals in the input array.

2. Sort Intervals by Start Time

Sort the intervals based on their starting values.
This will make it easier to detect overlaps by ensuring that any overlapping intervals are adjacent.

def merge_intervals(intervals: list) -> list:
    intervals.sort(key=lambda x: x[0])
    return intervals

3. Initialize Merged Intervals List

Create an empty list merged to store the merged intervals.
The list will eventually contain only the non-overlapping intervals.

def merge_intervals(intervals: list) -> list:
    intervals.sort(key=lambda x: x[0])
    merged = []  # List to store merged intervals
    return merged

4. Iterate Through Sorted Intervals

For each interval, check if it overlaps with the last interval in the merged list.
If it does overlap, merge the intervals by extending the end of the last interval in merged.
If it doesn’t overlap, simply add it to merged.

def merge_intervals(intervals: list) -> list:
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        # If merged is empty or there is no overlap, add interval
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # Merge the current interval with the last one in merged
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

5. Return Merged Intervals

After processing all intervals, return the merged list which contains only non-overlapping intervals.

def merge_intervals(intervals: list) -> list:
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

6. Consider Edge Cases

Edge cases include:
- Only one interval, which should be returned as-is.
- Non-overlapping intervals, where each interval is added to merged without modification.
- Intervals that completely overlap each other.