作者: | 来源:互联网 | 2023-09-14 12:34
referto: https:www.algoexpert.ioquestionsMerge%20Overlapping%20IntervalsProblemStatementSa
refer to: https://www.algoexpert.io/questions/Merge%20Overlapping%20Intervals
Problem Statement
Sample example
Analysis
step 1: sort the intervals by their start value
step 2: check if the end value of the previous interval is larger than the start value of the latter interval
Code
def mergeOverlappingIntervals(intervals):
# sort the intervals by startinf value. O(nlogn)
sortedIntervals = sorted(intervals, key = lambda x: x[0])
mergedIntervals = []# space: O(n)
currentInterval = sortedIntervals[0]#initialize the currentInterval as the first interval of the intervals
mergedIntervals.append(currentInterval)#initialize the mergedIntervals as the first interval of the intervals
for nextInterval in sortedIntervals:# for the first iteration, no update
_, currentIntervalEnd = currentInterval
nextIntervalStart, nextIntervalEnd = nextInterval
if currentIntervalEnd >= nextIntervalStart: # overlap found, update the end value of interval
currentInterval[1] = max(currentIntervalEnd, nextIntervalEnd)
else: # no overlap, add the current(nextInterval) into the mergedIntervals array
currentInterval = nextInterval
mergedIntervals.append(currentInterval)
return mergedIntervals
Time and Space complexity
O(nlogn) time complexity for sorting
O(n) space complexity for store the mergedIntervals(upper bound, all intervals kept)