Coding - Merge Intervals

Full Interview Question: "Coding - Merge Intervals"

Question: Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return the merged intervals.

Examples:

1. Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

2. Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Since intervals [1,4] and [4,5] overlap, merge them into [1,5].

Constraints:

• 0 <= intervals.length <= 2000
• intervals[i].length == 2
• 0 <= start_i < end_i <= 10^5

Hints:

• Sort the intervals based on the start time.
• Iterate through the sorted intervals and merge them if they overlap.

Solution: `python class Solution: def merge(self, intervals): if not intervals: return []

    # Sort intervals based on the start time
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        prev = merged[-1]
        
        # Check if there is an overlap
        if current[0] <= prev[1]:
            # Merge the current interval with the previous one
            merged[-1] = [prev[0], max(prev[1], current[1])]
        else:
            # No overlap, just add the current interval
            merged.append(current)
    
    return merged

`

Explanation:

1. First, we sort the intervals based on their start times.
2. We initialize a list merged with the first interval.
3. We iterate through the remaining intervals and check if the current interval overlaps with the last interval in merged.
4. If there is an overlap, we merge the two intervals by updating the end time of the last interval in merged.
5. If there is no overlap, we simply add the current interval to merged.
6. Finally, we return the merged list of intervals.

Source:

• LeetCode: Merge Intervals
• DarkInterview: Merge Intervals