Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
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.
Solution for Merge Intervals in python
Approach (Sorting + Merging)
1. Sort the intervals by their starting times.
2. Iterate through the sorted intervals and merge them:
• If the current interval overlaps with the last added interval (prev_end >= curr_start), merge them.
• Otherwise, add the current interval to the result.
def mergeIntervals(intervals):
if not intervals:
return []
# Step 1: Sort intervals based on start time
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]] # Initialize with the first interval
for curr_start, curr_end in intervals[1:]:
prev_start, prev_end = merged[-1] # Last added interval
if prev_end >= curr_start: # Overlapping intervals
merged[-1][1] = max(prev_end, curr_end) # Merge
else:
merged.append([curr_start, curr_end]) # No overlap, add as a new interval
return merged
# Example usage:
print(mergeIntervals([[1,3],[2,6],[8,10],[15,18]])) # Output: [[1,6],[8,10],[15,18]]
print(mergeIntervals([[1,4],[4,5]])) # Output: [[1,5]]Complexity Analysis
• Sorting takes O(n log n).
• Merging takes O(n).
• Overall time complexity: O(n log n).
• Space complexity: O(n) (for the merged list).