Leet Code 56. Merge Intervals — Explained Python3 Solution

Problem Description

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution

Obvious Solution

The obvious (and brute force) way is : assuming there are N intervals, pick the first interval and compare it with the rest N-1 intervals, if there is overlap, I will merge the overlapped interval into the first interval; after that, I should have M intervals where M≤N; then I pick the second interval from those M intervals and compare it with the rest M-1 intervals and repeat the same logic … until I reach the last interval.

In worst case (no overlap at all), each one needs to compare with the rest N-1, N - 2, N - 3, …. intervals and hence make the time complextiy O(N²).

To optimize it, I’m considering sorting the input intervals first. Actually this is my instinct for this kind of questions. The reason is sorting time complexity is normally treated as O(NlogN) if a quick sort is applied. This part itself is better than O(N²).

And this clue leads me to next section which is the best solution to me.

Best Solution (to me)

Now assuming I already sort the intervals. Let’s see what happen.

When I loop within the sorted intervals, I actually don’t need to compare current interval with the rest ALL intervals if I run into a non-overlapped interval.

Let me use an example like below to illustrate: assume input is [[1,4], [7,10][3,6],[9,13]].

After I sort it, it looks like:

When I compare the first 2, I merge them to [1,6]; and then when I compare [1,6] with [7,10], I find out 6<7 and they are not overlapped, I know instantly that [1,6] will never have overlap with any interval after [7,10](here is [9,13]) since those intervals are even farther to [3,6] than [7,10]. So I know for sure [1,6] is a settled(final) interval and can move forward to compare next interval ([7,10]) to intervals after next interval. In short, I need to do total 3 comparisons:

[1,4] with [3,6] => merge to [1,6]

[1,6] with [7,10]

[7,10] with [9,13]

Consider if I’m using brute force way to tackle [[1,4], [7,10][3,6],[9,13]]. I need to do 4 comparisons.

[1,4] with [7,10]

[1,4] with [3,6] => merge to [1,6] now the list becomes [[1,6],[7,10],[9,13]]

[1,6] with [9,13]

[7,10] with [9,13]

If I use an example input intervals without overlaps like [[5,6],[1,4],[11,13],[7,10]], the difference between these 2 solutions can be more dramatic: 3 vs 6.

That is it. Code time now. In below code, I will use a list named ret to store merged intervals. Whenever I come to an interval, I will try to merge it (if mergeable) with the last interval in ret, if that’s not possible, the current interval is an independent interval (to currently visited intervals), I will add it to the end of ret.

	class Solution:
	def merge(self, intervals: List[List[int]]) -> List[List[int]]:
	'''
	Detailed graphical explanation:
	https://medium.com/@edward.zhou/leet-code-56-merge-intervals-explained-python3-solution-89b3297e81a1
	I can compare each one of intervals against the other, it will be
	a n to n comparison and make the complexity O(n^2).
	If intervals are ordered by start times (complexity is O(nlogn)),
	then I just need to compare the two contious internals which is a
	O(n) work. Total complexity will be O(nlogn + n) = O(nlogn)
	'''
	intervals = sorted(intervals, key=lambda x:x[0])
	ret = []
	for i in intervals:
	newInterval = i
	#compare with the last one in ret
	if ret:
	if ret[-1][1] >= i[0]:
	#merge and then replace the last one in ret
	newInterval = ret.pop()
	if i[1] > newInterval[1]:
	newInterval[1] = i[1]
	ret.append(newInterval)
	return ret

view raw lc56.py hosted with ❤ by GitHub

Time & Space Complexity

As mentioned earlier, sorting’s complextiy is O(NlogN) while looping each interval for the comparison is O(N) so the total is O(NlogN).

In my above code, I use a ret list to store merged intervals which can take up to O(N).

Python 3 knowledge points

There is a line of code in above solution:

intervals = sorted(intervals, key=lambda x:x[0])

It may look confusing and below are related Python 3 knowledge points:

1. build-in function: sorted
2. lambda expression

Both of them are covered in my Python3 cheatsheet.

Extended Reading

1. 3 minutes to implement Quick Sort with Python: https://medium.com/@edward.zhou/3-minutes-to-implement-quick-sort-with-python-3-4b186dec23ce

2. Python3 cheatsheet:

https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549