algoadvance

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example:

  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: Intervals [1,4] and [4,5] are considered overlapping.

Clarifying Questions

  1. Input Size: What is the size range for the input array?
  2. Input Validity: Can we assume that the intervals are always given in a valid format (i.e., start is always less than or equal to end)?
  3. Edge Cases: How should the function handle empty input?

Strategy

  1. Sorting: First, sort the intervals based on the start time. This helps in merging intervals by comparing consecutive intervals.
  2. Merging: Initialize an empty list to store merged intervals.
    • Traverse through the sorted intervals:
      • If the list of merged intervals is empty or if the current interval does not overlap with the last merged interval, append it to the merged list.
      • If the current interval overlaps with the last merged interval, merge them by updating the end of the last merged interval to be the maximum end of both the last merged and current intervals.

Time Complexity

Code

Here is the Python code to solve the problem:

def merge(intervals):
    if not intervals:
        return []

    # Sort the intervals based on the start time
    intervals.sort(key=lambda x: x[0])

    merged_intervals = [intervals[0]]

    for current in intervals[1:]:
        last_merged = merged_intervals[-1]
        
        if current[0] <= last_merged[1]:  # If there's an overlap
            # Merge the intervals by updating the end of the last interval
            last_merged[1] = max(last_merged[1], current[1])
        else:
            # No overlap, just add the interval
            merged_intervals.append(current)
    
    return merged_intervals

This code first sorts the intervals based on the start time, then iteratively merges overlapping intervals, and finally returns the merged intervals.

Try our interview co-pilot at AlgoAdvance.com