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 considerred overlapping.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Starter code: class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        

Solutions:
class Solution:

	def merge(self, intervals):
		inters = sorted(intervals, key=lambda intval: intval.start)
		ret = []
		n = len(intervals)
		if n == 0:
			return ret
		s = inters[0].start
		e = inters[0].end
		for i in range(1, n):
			if inters[i].start <= e:
				e = max(inters[i].end, e)
			else:
				ret.append(Interval(s, e))
				s = inters[i].start
				e = inters[i].end
		ret.append(Interval(s, e))
		return ret