Untitled — Python Coding — Nerchuko Academy

Merge Overlapping Intervals

MEDIUM

Write a function to merge overlapping intervals in a list of tuples (or lists), where each tuple (start, end) represents an interval. The intervals should be merged if they overlap, producing a new list of non-overlapping intervals that cover all the input intervals.

Examples:

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].

Example 2:

Input: intervals = [[1,4], [4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Example 3:

Input: intervals = [[1,4], [0,4]]
Output: [[0,4]]

Example 4:

Input: intervals = [[1,4], [2,3]]
Output: [[1,4]]

Constraints:

1 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁴

Function Signature (Python):

from typing import List, Tuple

class Solution:
    # Using List[List[int]] as per LeetCode convention, but Tuple[int, int] is also common
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Your code here
        pass

Solution Explanation & Interview Strategy

The Goal: Imagine you have a list of time slots, like appointments: [(1,3), (2,6), (8,10), (15,18)]. If one appointment ends after another begins, they overlap. We want to combine these overlapping appointments into larger, continuous blocks.

(1,3) and (2,6) overlap because appointment 2 starts at time 2, which is before appointment 1 ends at time 3. They merge into (1,6).
(8,10) doesn't overlap with (1,6).
(15,18) doesn't overlap with (8,10).

So, the final merged list is [(1,6), (8,10), (15,18)].

Approach: Sort and Merge

This is the standard and most intuitive way to solve this problem.

Sort the Intervals: The first crucial step is to sort the intervals based on their start times. This ensures that we process intervals in an order that makes merging straightforward. If start times are equal, the order of end times doesn't strictly matter for this specific problem's logic but sorting by end time as a secondary key is fine.
Iterate and Merge:
- Initialize an empty list called merged_intervals.
- Add the first sorted interval to merged_intervals.
- Iterate through the rest of the sorted intervals (starting from the second one). For each current_interval:
  - Let last_merged_interval be the last interval in merged_intervals.
  - Check for overlap: If the current_interval's start time is less than or equal to the last_merged_interval's end time, they overlap.
    - Update the end time of last_merged_interval to be the maximum of its current end time and the current_interval's end time. This effectively extends the last merged interval to cover the current one.
  - No overlap: If they don't overlap, add the current_interval to the merged_intervals list as a new, separate interval.

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []

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

        merged_intervals = []
        merged_intervals.append(intervals[0]) # Add the first interval to start

        for i in range(1, len(intervals)):
            current_start, current_end = intervals[i]
            last_merged_start, last_merged_end = merged_intervals[-1]

            # Check for overlap: current_start <= last_merged_end
            if current_start <= last_merged_end:
                # Overlap exists, merge them by updating the end of the last merged interval
                merged_intervals[-1][1] = max(last_merged_end, current_end)
            else:
                # No overlap, add the current interval as a new one
                merged_intervals.append([current_start, current_end])
                
        return merged_intervals

# Example Usage:
# sol = Solution()
# print(sol.merge([[1,3], [2,6], [8,10], [15,18]])) # [[1,6], [8,10], [15,18]]
# print(sol.merge([[1,4], [4,5]]))                 # [[1,5]]

How it works (for `intervals = [[1,3], [2,6], [8,10]]`):

Sorted: `[[1,3], [2,6], [8,10]]` (already sorted by start time).
Initialize merged_intervals = [].
Add first interval: merged_intervals = [[1,3]].
Current interval [2,6]:
- last_merged_end = 3. current_start = 2.
- 2 <= 3 (overlap).
- Update merged_intervals[-1][1] to max(3, 6) = 6.
- merged_intervals is now [[1,6]].
Current interval [8,10]:
- last_merged_end = 6. current_start = 8.
- 8 <= 6 is false (no overlap).
- Add [8,10] to merged_intervals.
- merged_intervals is now [[1,6], [8,10]].
Loop ends. Return [[1,6], [8,10]].

Complexity Analysis:

Time Complexity: O(N log N), where N is the number of intervals. This is dominated by the sorting step. The iteration through the sorted intervals takes O(N) time.

Space Complexity: O(N) or O(log N) for sorting (depending on the sort algorithm's space usage, Python's Timsort is O(N) in worst-case for space). The merged_intervals list can also store up to N intervals in the case where no intervals overlap, so it contributes O(N) to space. If we consider the space used by the output as part of the complexity, it's O(N). If we only consider auxiliary space beyond the input and output, and the sort is in-place (or O(log N) space), then it's O(log N) or O(1) auxiliary space. Typically, for interview purposes, the space for the output list is included, leading to O(N).

Key Takeaways for Interviews:

Importance of Sorting: Clearly state that sorting by start times is the crucial first step. Explain why it simplifies the merging logic.
Overlap Condition: Be precise about how you define an overlap between two intervals [s1, e1] and [s2, e2] after sorting (i.e., s1 <= s2): they overlap if s2 <= e1.
Merging Logic: Explain how to update the end point of the last merged interval: new_end = max(last_merged_end, current_interval_end).
Edge Cases:
- Empty input list: Should return an empty list.
- Single interval: Should return the list with that single interval.
- No overlapping intervals: The original sorted list should be returned.
- All intervals overlap / are contained: Should return a single merged interval.
Complexity: Be ready to discuss the O(N log N) time complexity due to sorting and O(N) space complexity.