Merge Intervals
Merge Intervals. An interval is a representation of a range of values along a number line. For example, [1,3] represents all numbers between 1 and 3, inclusive. Given a collection of intervals, the task is to merge all overlapping intervals.
For example, consider the intervals [1,3],[2,6],[8,10],[15,18]. The function should return merged intervals where overlapping intervals are combined. In this case, intervals [1,3] and [2,6] overlap, so they should be merged into [1,6].
Examples
intervals = [[1,3], [2,6], [8,10], [15,18]] output: [[1,6], [8,10], [15,18]] intervals = [[1,4], [4,5]] output: [[1,5]] intervals = [[1,4], [2,3]] output: [[1,4]] intervals = [[1,2], [3,4], [5,6], [7,8]] output: [[1,2], [3,4], [5,6], [7,8]]
The mergeIntervals function takes an array of intervals and merges all overlapping intervals into a single interval. The process involves sorting the intervals by their start times and then iterating through them to merge where necessary. Here is a step-by-step breakdown:
- Initial Check: If the input array is empty, the function immediately returns an empty array, as there are no intervals to merge.
- Sorting: The intervals are sorted by their start times. This ensures that intervals can be processed in a linear sweep, merging adjacent intervals when they overlap.
- Merging Intervals: Initialize a result list with the first interval. Then, iterate through the sorted intervals starting from the second interval. For each interval, compare it with the last interval in the result list. If the current interval overlaps with the last interval in the result (i.e., the start of the current interval is less than or equal to the end of the last interval), merge them by updating the end of the last interval in the result to the maximum end time of both intervals. If there is no overlap, add the current interval to the result list as a separate interval.
- Return the Result: After processing all intervals, the result list contains the merged intervals.
def mergeIntervals(intervals):
if not intervals:
return []
# Sort intervals by the start time
intervals.sort(key=lambda x: x[0])
# Initialize the result list with the first interval
result = [intervals[0]]
for i in range(1, len(intervals)):
current_interval = result[-1]
next_interval = intervals[i]
# If the current interval overlaps with the next interval, merge them
if current_interval[1] >= next_interval[0]:
current_interval[1] = max(current_interval[1], next_interval[1])
else:
# Otherwise, add the next interval to the result
result.append(next_interval)
return resultTime Complexity: The dominant factor in the time complexity is the sorting step, which takes O(n log n), where n is the number of intervals. The merging process involves a single pass through the sorted intervals, which takes O(n) time. Therefore, the overall time complexity is O(n log n).
Space Complexity: The space complexity is O(n), which accounts for the space required to store the result list. This is because, in the worst case, none of the intervals overlap, and the result list will contain all the original intervals.
In this mock interview video, Lewin (Dropbox SWE), answers the interview question, "Given an array of intervals, merge the overlapping intervals and return an array of the non-overlapping intervals that cover all intervals in the input."
const mergeIntervals = (intervals) => { const compare = (a, b) => { if(a[0] < b[0]) return -1 else if (a[0] > b[0]) return 1 else if(a[0] === b[0]) { return a[1] - b[1] } } let current = [] const result = [] const sorted = intervals.sort(compare) for(let i = 0; i < sorted.length; i++) { if(current) { const [a, b] = [current,sorted[i]] if(a[1] >= b[0]) current[1] = b[1] else { if(current.length > 0) result.push(current) current = b } } else current = sorted[i] } result.push(current) return result }