To solve this problem, we need to merge overlapping or adjacent intervals into a single interval. The key insight here is to first sort the intervals by their start time, which allows us to efficiently merge intervals as we iterate through the sorted list.

Approach

1. Check for Empty Input: If the input list of intervals is empty, return an empty list immediately.
2. Sort Intervals: Sort the intervals based on their start value. This ensures that we can process intervals in a sequential manner where overlapping intervals are adjacent.
3. Merge Intervals:
   • Initialize the merged list with the first interval from the sorted list.
   • For each subsequent interval, compare its start with the end of the last interval in the merged list:
     • If the current interval's start is less than or equal to the last interval's end, they overlap. Update the last interval's end to the maximum of the two ends.
     • If they do not overlap, add the current interval to the merged list.

Solution Code

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

    # Sort intervals by their start value
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    merged = [sorted_intervals[0]]

    for current in sorted_intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:
            # Overlapping intervals, merge them
            last[1] = max(last[1], current[1])
        else:
            # Non-overlapping, add to merged list
            merged.append(current)

    return merged

Explanation

• Sorting: By sorting the intervals, we ensure that any overlapping or adjacent intervals are next to each other. This simplifies the merging process as we only need to check the last merged interval against the current one.
• Merging: For each interval, we either merge it with the last interval in the merged list (if they overlap) or add it as a new interval (if they don't). This approach runs in O(n log n) time due to the sorting step, where n is the number of intervals. The space complexity is O(n) for storing the merged intervals (worst case when no intervals overlap).

This solution efficiently handles all cases, including overlapping, adjacent, and non-overlapping intervals, and works for edge cases like empty input or single intervals.

作者声明:本文包含人工智能生成内容。