leetcode_gym/_problems/mergeIntervals.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Merge Intervals	2020-06-03	intervals	https://leetcode.com/problems/merge-intervals/	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 %}