65 lines
2.2 KiB
Markdown
65 lines
2.2 KiB
Markdown
|
---
|
||
|
|
layout: page
|
||
|
|
title: Merge Intervals
|
||
|
|
last_solved: 2020-06-03
|
||
|
|
category: intervals
|
||
|
|
leetcode_url: https://leetcode.com/problems/merge-intervals/
|
||
|
|
status: Attempted
|
||
|
|
---
|
||
|
|
|
||
|
|
###### Problem:
|
||
|
|
|
||
|
|
Turn ```[[1,3],[2,6],[8,10],[15,18]]``` into ```[[1,6],[8,10],[15,18]]```
|
||
|
|
|
||
|
|
###### Solution:
|
||
|
|
|
||
|
|
As you're looping thru, compare the prev's interval with the current interval.
|
||
|
|
|
||
|
|
If the prev[1] > curr[0], that means there's a merge and you just replace it with the ```max(prev[1],curr[1])```
|
||
|
|
|
||
|
|
Otherwise, just append to the merged output array.
|
||
|
|
|
||
|
|
O(n*logn) time (linear time to go thru intervals, sort at beginning takes logn)
|
||
|
|
O(n) space
|
||
|
|
|
||
|
|
{% highlight python %}
|
||
|
|
|
||
|
|
|
||
|
|
intervals = [[1,3],[2,6],[8,10],[15,18]]
|
||
|
|
|
||
|
|
|
||
|
|
def merge(intervals):
|
||
|
|
|
||
|
|
intervals.sort(key=lambda x: x[0])
|
||
|
|
|
||
|
|
merged = []
|
||
|
|
|
||
|
|
# add the first interval to merged[]
|
||
|
|
merged.append(intervals[0])
|
||
|
|
|
||
|
|
for interval in intervals:
|
||
|
|
|
||
|
|
print(interval)
|
||
|
|
|
||
|
|
if merged[-1][1] < interval[0]: # no merge, [2,6] compared to [8,10]
|
||
|
|
|
||
|
|
print('no merge')
|
||
|
|
merged.append(interval)
|
||
|
|
else:
|
||
|
|
print('merge', merged[-1][1], interval[1])
|
||
|
|
merged[-1][1] = max(merged[-1][1], interval[1] ) # choose the max of "prev" (aka: merged[-1]) or the current interval
|
||
|
|
|
||
|
|
print()
|
||
|
|
|
||
|
|
print(merged)
|
||
|
|
|
||
|
|
|
||
|
|
{% endhighlight %}
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|