LC 0056 [M] Merge Intervals - ALawliet/algorithms GitHub Wiki
merge (OVERLAPPING) intervals
sort by starts, check if cur start comes before last end = overlap, merged interval is [last start, max(last end, cur end]
res[-1][1] = max(res[-1][1], x[1])
# or
last_interval = res.pop()
merged_interval = [last_interval[0], max(last_interval[1], cur_interval[1])] # keep start, extend end
res.append(merged_interval)
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
res = []
intervals.sort(key=lambda x: x[0]) # sort by starts
for x in intervals:
start, end = x
if res and start <= res[-1][1]: # cur start is before last end (is overlap)
# keep the last start
res[-1][1] = max(res[-1][1], end) # but last end is stretched to max(last end, cur end)
else:
res.append(x)
return res