Merge Overlapping Intervals
Problem
You have some overlapping closed intervals and you want to merge them. What is the algorithm for this?
Solution
Here are some examples with input and output:
Input1: Intervals = [[1, 3], [2, 4], [6, 8], [9, 10]]
Output1: [[1, 4], [6, 8], [9, 10]]
Input2: Intervals = [[6, 8], [1, 9], [2, 4], [4, 7]]
Output2: [[1, 9]]
And the algorithm:
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
# Sort the array on the basis of start values of intervals.
intervals.sort()
stack = []
# insert first interval into stack
stack.append(intervals[0])
for curr in intervals[1:]:
# Check for overlapping interval,
# if interval overlap
if stack[-1][0] <= curr[0] <= stack[-1][-1]:
stack[-1][-1] = max(stack[-1][-1], curr[-1])
else:
stack.append(curr)
#
#
return stack
Links
- https://www.geeksforgeeks.org/merging-intervals/ (found here)
Categories: python
algorithms, intervals, merge
Comments (0)
Leave a comment