Intervals
Merge Intervals
DESCRIPTION (inspired by Leetcode.com)
Write a function to consolidate overlapping intervals within a given array intervals, where each interval intervals[i] consists of a start time starti and an end time endi.
Two intervals are considered overlapping if they share any common time, including if one ends exactly when another begins (e.g., [1,4] and [4,5] overlap and should be merged into [1,5]).
The function should return an array of the merged intervals so that no two intervals overlap and all the intervals collectively cover all the time ranges in the original input.
Input:
intervals = [[3,5],[1,4],[7,9],[6,8]]
Output:
[[1,5],[6,9]]
Explanation: The intervals [3,5] and [1,4] overlap and are merged into [1,5]. Similarly, [7,9] and [6,8] overlap and are merged into [6,9].
Explanation
def mergeIntervals(intervals):sortedIntervals = sorted(intervals, key=lambda x: x[0])merged = []for interval in sortedIntervals:if not merged or interval[0] > merged[-1][1]:merged.append(interval)else:merged[-1][1] = max(interval[1], merged[-1][1])return merged
intervals[1]
0 / 1
def mergeIntervals(intervals):sortedIntervals = sorted(intervals, key=lambda x: x[0])merged = []for interval in sortedIntervals:if not merged or interval[0] > merged[-1][1]:merged.append(interval)else:merged[-1][1] = max(interval[1], merged[-1][1])return merged
intervals[2]
0 / 1
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n * logn) where n is the number of intervals. The time complexity is dominated by the sorting step.
Space Complexity: O(n) where n is the number of intervals. We need space for the merged output array.
Solution
def mergeIntervals(intervals):sortedIntervals = sorted(intervals, key=lambda x: x[0])merged = []for interval in sortedIntervals:if not merged or interval[0] > merged[-1][1]:merged.append(interval)else:merged[-1][1] = max(interval[1], merged[-1][1])return merged
merge intervals
0 / 10
Mark as read
Unlock Premium Coding Content
On This Page
Your account is free and you can post anonymously if you choose.