56. Merge Intervals
Model: qwen3.5:9b
Topics: Array,Sort
FAANG asked: 1
Acceptance rate: 41.4%
Problem Breakdown
We are given a list of intervals, where each interval is defined by a start and end point [start_i, end_i]. The goal is to consolidate any overlapping or adjacent ranges into single continuous blocks. We must return the resulting non-overlapping intervals that cover all original input data without gaps (except for intentional breaks between merged groups).
Inputs: A list of lists intervals, where each inner list has exactly two integers [start, end].
Outputs: A new list containing only the merged, non-overlapping intervals.
Implicit Constraints & Edge Cases:
- Ordering: The input is not guaranteed to be sorted by start time; sorting is required for efficiency.
- Overlap Definition: Based on Example 2 (
[1,4]and[4,5]merge), touching endpoints count as overlapping (inclusive boundary). Condition:next_start <= current_end. - Data Range: Values are non-negative () and fit within standard integer limits. No overflow issues expected given constraints up to .
Intuition
A naive brute-force approach would be to compare every interval with every other interval in the list (nested loops). For each pair, we check if they overlap and merge them if necessary. This results in a time complexity of . Given the constraint , an solution would perform roughly operations, which risks Time Limit Exceeded (TLE) on larger inputs or slower languages like Python.
The key insight is that overlap relationships are transitive and local. If we sort the intervals by their start times, any interval overlapping with a previous one must be adjacent to it in the sorted list. This transforms the problem into a linear scan:
- Sort all intervals based on
start. - Iterate through the sorted list once.
- Maintain a “current merged” window. If the next interval starts before or exactly when the current one ends, they overlap; we extend our end point to cover both. Otherwise, the previous group is complete and finalized, so we start a new group.
This greedy strategy ensures that by the time we reach an interval with no overlaps, all preceding intervals have been fully processed into merged groups.
Approach
- Sort: Sort
intervalsin ascending order of their starting points (start). If starts are equal, sorting by end point is secondary but not strictly necessary for correctness here (though Python’s stable sort handles it naturally). - Initialize Result List: Create a list to store the merged intervals. Initialize it with the first interval from the sorted input as our “active” merge target.
- Iterate & Merge: Loop through the remaining intervals starting from index
1. For each new interval:- Compare its start time against the end time of the last added interval in our result list (
merged[-1]). - If
new_start <= merged_end: There is an overlap. Update the end point of that last interval to bemax(merged_end, new_end). This effectively extends the current range. - If
new_start > merged_end: No overlap exists with the previous group. Append this new interval as a fresh entry in our result list.
- Compare its start time against the end time of the last added interval in our result list (
- Return: After iterating through all intervals, return the constructed list of non-overlapping ranges.
Complexity Analysis
- Time Complexity: . The dominant operation is sorting the input array ( items), which takes . The subsequent linear scan to merge intervals takes . Thus, total time is dominated by sort complexity.
- Space Complexity: (auxiliary). Python’s Timsort implementation uses a stack for sorting recursion/merges which requires logarithmic space relative to input size. We do not count the output list in auxiliary space as it represents the required result, but strictly speaking, we allocate memory proportional to the number of merged intervals in the worst case () if counting total storage including return value. However, excluding the output array, extra working space is minimal/constant relative to .
Solution
def merge(intervals):
# Sort by start time first; Python sorts tuples/lists element-wise naturally
intervals.sort(key=lambda x: x[0])
if not intervals:
return []
merged = [intervals[0]] # Initialize with the first interval
for current in intervals[1:]:
last_start, last_end = merged[-1]
curr_start, curr_end = current
# Check overlap condition (inclusive boundary)
if curr_start <= last_end:
# Overlap exists; extend the end of the previous interval
# to cover both ranges. We modify in-place for efficiency.
merged[-1][1] = max(last_end, curr_end)
else:
# No overlap; start a new independent interval group
merged.append(current)
return merged
Edge Cases Handled
- Single Interval: The loop
intervals[1:]is empty. Code returns[intervals[0]], which is correct. - No Overlaps (Disjoint): Every interval triggers the
elsebranch, appending to result list unchanged. Correctly preserves all intervals. - Fully Contained Intervals: E.g.,
[1, 5]and[2, 3]. Sorted order keeps them adjacent. The logic updates end/max correctly (though here start > prev_start). If input was[[1,4], [2,6]], it merges to[1,6]. - Touching Intervals: E.g.,
[1,4]and[4,5]. Conditioncurr_start <= last_endevaluates true (4 <= 4). They merge into[1,5]. Matches Example 2 requirement.