Merge Intervals

Medium

Google

12 views

Topics:

ArraysGreedy Algorithms

You are given a list of time intervals represented as an array of arrays, where each inner array contains the start and end time of an interval. The goal is to merge all overlapping intervals and return a new array containing only the non-overlapping intervals that cover all the intervals in the input.

Describe a brute-force approach to solve this problem. What is the time complexity of the brute-force approach?
Can you suggest a more efficient algorithm to merge the overlapping intervals? Explain the steps involved in your algorithm. What is the time complexity of the optimized algorithm?
Show me the code for your solution. Explain the code line by line.
What are the edge cases that need to be considered while implementing the interval merging algorithm?

For example:

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

Merge Intervals

Medium

Google

12 views

Topics:

ArraysGreedy Algorithms

You are given a list of time intervals represented as an array of arrays, where each inner array contains the start and end time of an interval. The goal is to merge all overlapping intervals and return a new array containing only the non-overlapping intervals that cover all the intervals in the input.

Describe a brute-force approach to solve this problem. What is the time complexity of the brute-force approach?
Can you suggest a more efficient algorithm to merge the overlapping intervals? Explain the steps involved in your algorithm. What is the time complexity of the optimized algorithm?
Show me the code for your solution. Explain the code line by line.
What are the edge cases that need to be considered while implementing the interval merging algorithm?

For example:

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the intervals in the input array be unsorted? If so, should I sort them first?
What is the expected behavior if the input array `intervals` is null or empty?
Can the start or end values of an interval be negative? Are they always integers?
If intervals are considered overlapping when they only share an endpoint (e.g., [1, 2] and [2, 3]), should they be merged?
Is there a specific order in which the merged intervals should be returned (e.g., sorted by start time)?

Brute Force Solution

Approach

We have a list of time periods, like appointments, each with a start and end time. The brute force way to merge these overlapping periods is to check every possible pair of periods to see if they overlap and can be combined. This is a very thorough, but not very efficient approach.

Here's how the algorithm would work step-by-step:

Take the first time period from the list.
Compare it to every other time period in the list to see if they overlap at all.
If the first period overlaps with another period, combine them into a single, bigger period that covers both of them.
After comparing the first period to all the others, move to the second time period in the original list.
Repeat the process of comparing the second period to all the *other* time periods (including the potentially combined periods from the previous steps).
Keep doing this for every time period in the original list, making sure you're always comparing each period with all the others.
At the end, you'll have a new list of time periods where any overlapping intervals have been merged together. Some original time periods might completely disappear if they were merged into larger ones.

Code Implementation

def merge_intervals_brute_force(intervals): 
    merged_intervals = intervals[:] 
    number_of_intervals = len(intervals)

    for i in range(number_of_intervals): 
        for j in range(number_of_intervals): 
            # Avoid comparing an interval with itself
            if i == j: 
                continue

            first_interval = merged_intervals[i] 
            second_interval = merged_intervals[j] 

            # Check for valid intervals
            if first_interval is None or second_interval is None:
                continue

            first_start = first_interval[0] 
            first_end = first_interval[1] 
            second_start = second_interval[0] 
            second_end = second_interval[1] 

            # Check if the intervals overlap
            if (first_start <= second_end and first_end >= second_start): 

                # Merge overlapping intervals to encompass both ranges
                new_start = min(first_start, second_start) 
                new_end = max(first_end, second_end)

                merged_intervals[i] = [new_start, new_end] 
                merged_intervals[j] = None 

    # Filter out any intervals set to None (merged intervals) 
    result = [interval for interval in merged_intervals if interval is not None]

    return result

Big(O) Analysis

Time Complexity

O(n²) – The provided algorithm iterates through each of the n intervals in the input list. For each interval, it compares it with every other interval in the list to check for overlaps and potentially merge them. This comparison process involves checking roughly n intervals for each of the n original intervals. Therefore, the number of comparisons grows proportionally to n * n which simplifies to O(n²).

Space Complexity

O(N) – The provided brute force merging algorithm, as described, modifies the list of intervals in-place and potentially creates new, merged intervals. Although the description alludes to modifications, the critical aspect impacting space complexity is the new list of time periods where overlapping intervals have been merged. In the worst-case scenario, where no intervals initially overlap, we'd need to store up to N intervals in a new list as intermediate results. Therefore, the algorithm utilizes auxiliary space proportional to the input size N, where N is the number of input intervals, for storing the potentially merged intervals, resulting in O(N) space complexity.

Optimal Solution

Approach

The most efficient way to merge intervals involves sorting them first, then combining overlapping intervals as you go. Sorting allows you to process intervals in order, making it easy to identify overlaps and create the merged set.

Here's how the algorithm would work step-by-step:

First, put all the intervals in order based on their starting points. This way, you're dealing with them sequentially.
Start with the first interval and compare it to the next one.
If the next interval overlaps with the current one, merge them into a single, larger interval that covers both.
If they don't overlap, keep the current interval as it is and move on to the next interval in the list.
Continue this process of comparing and merging until you've gone through all the intervals.
The result is a new list of intervals where all overlapping intervals have been combined.

Code Implementation

def merge_intervals(intervals):
    # Sort the intervals based on their start times.
    intervals.sort(key=lambda interval: interval[0])

    merged_intervals = []
    
    for interval in intervals:
        # If the list of merged intervals is empty or if the current
        # interval does not overlap with the last interval, append it.
        if not merged_intervals or merged_intervals[-1][1] < interval[0]:
            merged_intervals.append(interval)

        else:
            # Otherwise, there is overlap, so we merge the current and previous
            # intervals, updating the end time of the last merged interval
            merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1])

    return merged_intervals

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this algorithm is sorting the input list of n intervals. Sorting algorithms like merge sort or quicksort have a time complexity of O(n log n). After sorting, we iterate through the sorted list once, comparing each interval to the previous one to merge overlaps. This linear pass takes O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The algorithm sorts the input intervals in place, which, depending on the sorting algorithm used, might require auxiliary space. After sorting, the algorithm creates a new list to store the merged intervals. In the worst-case scenario, where no intervals overlap, this new list will contain all N intervals from the input. Therefore, the space complexity is O(N) due to the space required for storing the merged intervals list.

Edge Cases

Case	How to Handle
Empty input intervals array	Return an empty list, as there are no intervals to merge.
Single interval in the input array	Return the input array as is, since there's nothing to merge.
Intervals are already non-overlapping and sorted	After sorting the intervals, no merging will occur and the original sorted list will be returned.
Intervals are in reverse sorted order	The sorting step ensures correct merging regardless of the initial order.
Intervals with identical start and end points (e.g., [1, 1])	These intervals should be handled correctly during the merging process.
Intervals with large integer values causing potential overflow during comparisons	Ensure the comparison logic uses appropriate data types and handles potential overflow issues.
Intervals that completely overlap (e.g., [1, 5] and [2, 4])	The merging logic should correctly reduce these to the encompassing interval [1, 5].
Input contains intervals with negative numbers	The solution should correctly handle negative start and end points after sorting.