Given a collection of Intervals, the task is to merge all of the overlapping Intervals.
Example 1:
Input:
Intervals = {{1,3},{2,4},{6,8},{9,10}}
Output: {{1, 4}, {6, 8}, {9, 10}}
Explanation: Given intervals: [1,3],[2,4]
[6,8],[9,10], we have only two overlapping
intervals here,[1,3] and [2,4]. Therefore
we will merge these two and return [1,4],
[6,8], [9,10].
Example 2:
Input:
Intervals = {{6,8},{1,9},{2,4},{4,7}}
Output: {{1, 9}}
Your Task:
Complete the function overlappedInterval() that takes the list N intervals as input parameters and returns sorted list of intervals after merging.
Expected Time Complexity: O(N*Log(N)).
Expected Auxiliary Space: O(Log(N)) or O(N).
Constraints:
1 ≤ N ≤ 100
0 ≤ x ≤ y ≤ 1000

Difficulty: MEDIUM
Tags: String algorithms

Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(N*Log(N)).
Expected Auxiliary Space: O(Log(N)) or O(N).

Starter code:
class Solution:
	def overlappedInterval(self, Intervals):
		#Code here

Solutions:
class Solution:

	def overlappedInterval(self, Intervals):
		i = 0
		Intervals.sort()
		ans = []
		while i < len(Intervals):
			first = Intervals[i][0]
			last = Intervals[i][1]
			while i < len(Intervals) - 1 and Intervals[i + 1][0] <= last:
				last = max(last, Intervals[i + 1][1])
				i += 1
			ans.append([first, last])
			i += 1
		return ans


class Solution:

	def overlappedInterval(self, Intervals):
		j = Intervals
		j.sort(key=lambda i: i[0])
		out = [j[0]]
		for (start, end) in j[1:]:
			endpoint = out[-1][1]
			if start <= endpoint:
				out[-1][1] = max(out[-1][1], end)
			else:
				out.append([start, end])
		return out


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		stack = [Intervals[0]]
		for (v1, v2) in Intervals[1:]:
			if stack[-1][1] >= v1:
				stack[-1][1] = max(v2, stack[-1][1])
			else:
				stack.append([v1, v2])
		return stack


((1, 9), (2, 4), (4, 7), (6, 8))

class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		answer = []
		for (index, element) in enumerate(Intervals):
			if index == 0 or answer[-1][1] < element[0]:
				answer.append(element)
			else:
				answer[-1][1] = max(element[1], answer[-1][1])
		return answer


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort(key=lambda x: x[0])
		list1 = [Intervals[0]]
		for (v1, v2) in Intervals[1:]:
			if list1[-1][1] >= v1:
				list1[-1][1] = max(list1[-1][1], v2)
			else:
				list1.append([v1, v2])
		return list1


class Solution:

	def overlappedInterval(self, it):
		i = 0
		it.sort()
		l = []
		while i < len(it):
			y = it[i][0]
			x = it[i][1]
			while i < len(it) - 1 and it[i + 1][0] <= x:
				x = max(x, it[i + 1][1])
				i += 1
			l.append([y, x])
			i += 1
		return l


class Solution:

	def overlappedInterval(self, Intervals):

		def sort_func(ele):
			return ele[0]
		from collections import deque
		Intervals.sort(key=sort_func)
		stack = deque([Intervals[0]])
		for i in Intervals:
			if i[0] > stack[-1][1]:
				stack.append(i)
			elif i[0] <= stack[-1][1]:
				if i[1] > stack[-1][1]:
					stack[-1][1] = i[1]
		return stack


class Solution:

	def get_start_interval(self, interval):
		return interval[0]

	def overlappedInterval(self, Intervals):
		Intervals = sorted(Intervals, key=self.get_start_interval)
		result = [Intervals[0]]
		for i in range(len(Intervals)):
			n = len(result)
			if Intervals[i] not in result:
				if Intervals[i][0] <= result[n - 1][1]:
					result[n - 1][1] = max(result[n - 1][1], Intervals[i][1])
				else:
					result.append(Intervals[i])
		return result


class Solution:

	def overlappedInterval(self, a):
		a.sort()
		res = []
		res.append(a[0])
		for i in range(1, len(a)):
			if res[-1][1] < a[i][0]:
				res.append(a[i])
			elif res[-1][0] <= a[i][0] and res[-1][1] >= a[i][0]:
				res[-1][1] = max(res[-1][1], a[i][1])
		return res


class Solution:

	def overlappedInterval(self, arr):
		n = len(arr)
		arr.sort()
		ans = []
		for i in range(n):
			if len(ans) == 0 or arr[i][0] > ans[-1][1]:
				ans.append(arr[i])
			else:
				ans[-1][1] = max(ans[-1][1], arr[i][1])
		return ans


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort(key=lambda x: x[0])
		ans = [Intervals[0]]
		n = len(Intervals)
		x = ans[0][1]
		for i in range(1, n):
			if x < Intervals[i][0]:
				ans.append(Intervals[i])
				x = ans[-1][1]
			elif x < Intervals[i][1]:
				ans[-1][1] = Intervals[i][1]
				x = ans[-1][1]
		return ans


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort()
		(a, b) = intervals[0]
		ans = []
		for i in intervals[1:]:
			if a <= i[0] <= b:
				b = max(b, i[1])
			else:
				ans.append([a, b])
				(a, b) = i
		ans.append([a, b])
		return ans


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort(key=lambda x: x[0])
		stack = []
		stack.append(intervals[0])
		for i in range(1, len(intervals)):
			top = stack[-1]
			if intervals[i][0] > top[1]:
				stack.append(intervals[i])
			else:
				top[1] = max(top[1], intervals[i][1])
		return stack


class Solution:

	def overlappedInterval(self, Intervals):
		res = []
		n = len(Intervals)
		if n == 0:
			return res
		Intervals.sort()
		curr = Intervals[0]
		for i in range(1, n):
			if curr[1] < Intervals[i][0]:
				res.append(curr)
				curr = Intervals[i]
			else:
				curr[1] = max(curr[1], Intervals[i][1])
		res.append(curr)
		return res


class Solution:

	def overlappedInterval(self, Intervals):
		idx = 0
		Intervals.sort()
		for i in range(1, n):
			if Intervals[idx][1] >= Intervals[i][0]:
				Intervals[idx] = [Intervals[idx][0], max(Intervals[idx][1], Intervals[i][1])]
			else:
				idx += 1
				Intervals[idx] = Intervals[i]
		return Intervals[0:idx + 1]


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		stack = []
		stack.append(Intervals[0])
		for i in range(1, len(Intervals)):
			if stack[-1][1] >= Intervals[i][0]:
				ele = stack.pop(-1)
				stack.append([ele[0], max(ele[1], Intervals[i][1])])
			else:
				stack.append(Intervals[i])
		return stack


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort(key=lambda x: x[0])
		currentLeft = intervals[0][0]
		currentRight = intervals[0][1]
		result = list()
		for (index, interval) in enumerate(intervals[1:]):
			if interval[0] < currentLeft and interval[1] < currentLeft:
				result.append(interval)
			elif interval[0] <= currentRight:
				currentLeft = min(currentLeft, interval[0])
				currentRight = max(currentRight, interval[1])
			else:
				result.append([currentLeft, currentRight])
				currentLeft = interval[0]
				currentRight = interval[1]
		result.append([currentLeft, currentRight])
		return result


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort(key=lambda x: x[0])
		prev = Intervals[0]
		ans = []
		for i in range(1, len(Intervals)):
			if Intervals[i][0] <= prev[1]:
				prev = [prev[0], max(Intervals[i][1], prev[1])]
			else:
				ans.append(prev)
				prev = Intervals[i]
		ans.append(prev)
		return ans


class Solution:

	def overlappedInterval(self, Intervals):
		res = []
		if Intervals == 0 or Intervals == None:
			return res
		Intervals.sort()
		temp = Intervals[0]
		for i in Intervals:
			if i[0] <= temp[1]:
				temp[1] = max(i[1], temp[1])
			else:
				res.append(temp)
				temp = i
		res.append(temp)
		return res


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		merged = []
		for i in Intervals:
			if not merged or merged[-1][1] < i[0]:
				merged.append(i)
			else:
				merged[-1][1] = max(merged[-1][1], i[1])
		return merged


class Solution:

	def overlappedInterval(self, Intervals):
		if len(Intervals) == 0:
			return []
		Intervals.sort()
		result = [Intervals[0]]
		for x in range(1, len(Intervals)):
			if result[-1][1] >= Intervals[x][0]:
				prev = result.pop(-1)
				result.append([prev[0], max(prev[1], Intervals[x][1])])
			else:
				result.append(Intervals[x])
		return result


from operator import itemgetter

class Solution:

	def overlappedInterval(self, Intervals):
		if len(Intervals) == 0:
			return []
		Intervals = sorted(Intervals, key=itemgetter(0))
		result = [Intervals[0]]
		count = 0
		for x in range(1, len(Intervals)):
			if result[count][1] >= Intervals[x][0]:
				prev = result.pop(count)
				result.append([prev[0], max(prev[1], Intervals[x][1])])
			else:
				result.append(Intervals[x])
				count += 1
		return result


from bisect import bisect_left

class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort()
		stack = [intervals[0]]
		for k in range(1, len(intervals)):
			(a, b) = stack[-1]
			i = intervals[k]
			if b >= i[0]:
				b = max(b, i[1])
				stack[-1] = (a, b)
			else:
				stack.append(i)
		return stack


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort()
		stack = []
		stack.append(intervals[0])
		for i in intervals[1:]:
			if stack[-1][0] <= i[0] <= stack[-1][-1]:
				stack[-1][-1] = max(stack[-1][-1], i[-1])
			else:
				stack.append(i)
		return stack


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort(key=lambda x: x[0])
		res = [Intervals[0]]
		n = len(Intervals)
		for i in range(1, n):
			if res[-1][-1] >= Intervals[i][0]:
				res[-1][1] = max(res[-1][-1], Intervals[i][-1])
			else:
				res.append(Intervals[i])
		return res


class Solution:

	def overlappedInterval(self, Intervals):
		ans = []
		if len(Intervals) == 0:
			return []
		Intervals.sort()
		temp_it = Intervals[0]
		for i in range(1, len(Intervals)):
			if temp_it[1] >= Intervals[i][0]:
				temp_it[1] = max(temp_it[1], Intervals[i][1])
			else:
				ans.append(temp_it)
				temp_it = Intervals[i]
		ans.append(temp_it)
		return ans


class Solution:

	def overlappedInterval(self, Intervals):
		res = []
		Intervals.sort()
		temp = Intervals[0]
		for i in range(0, len(Intervals)):
			if Intervals[i][0] >= temp[0] and Intervals[i][0] <= temp[1]:
				lis = []
				lis.append(temp[0])
				lis.append(max(temp[1], Intervals[i][1]))
				temp = list(lis)
			else:
				res.append(temp)
				temp = Intervals[i]
		if temp != []:
			res.append(temp)
			temp = []
		return res


class Solution:

	def overlappedInterval(self, Intervals):
		l = []
		Intervals.sort()
		n = len(Intervals)
		for i in range(n):
			if len(l) == 0 or Intervals[i][0] > l[-1][1]:
				l.append(Intervals[i])
			else:
				l[-1][1] = max(l[-1][1], Intervals[i][1])
		return l


class Solution:

	def overlappedInterval(self, arr):
		ans = []
		arr.sort(key=lambda x: x[0])
		for i in arr:
			if len(ans) > 0:
				if ans[-1][1] >= i[0]:
					ans[-1][1] = max(i[1], ans[-1][1])
				else:
					ans.append(i)
			else:
				ans.append(i)
		return ans


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort(key=lambda i: i[0])
		output = [Intervals[0]]
		for (start, end) in Intervals[1:]:
			lastend = output[-1][1]
			if start <= lastend:
				output[-1][1] = max(end, lastend)
			else:
				output.append([start, end])
		return output


class Solution:

	def overlappedInterval(self, Intervals):
		if not Intervals:
			return Intervals
		Intervals.sort()
		current_interval = Intervals[0]
		merged_intervals = []
		for interval in Intervals:
			if interval[0] <= current_interval[1]:
				current_interval[1] = max(current_interval[1], interval[1])
			else:
				merged_intervals.append(current_interval)
				current_interval = interval
		merged_intervals.append(current_interval)
		return merged_intervals


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort()
		stack = []
		for i in range(len(intervals)):
			if not stack or stack[-1][1] < intervals[i][0]:
				stack.append(intervals[i])
			else:
				stack[-1][1] = max(stack[-1][1], intervals[i][1])
		return stack


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort(key=lambda x: x[0])
		merged = []
		for interval in intervals:
			if not merged or merged[-1][1] < interval[0]:
				merged.append(interval)
			else:
				merged[-1][1] = max(merged[-1][1], interval[1])
		return merged


class Solution:

	def overlappedInterval(self, arr):
		arr.sort()
		i = 0
		while i < len(arr) - 1:
			a = i + 1
			if arr[i][1] < arr[a][0]:
				i += 1
			elif arr[i][1] >= arr[a][1]:
				arr.pop(a)
			else:
				arr[i][1] = arr[a][1]
				arr.pop(a)
		return arr


class Solution:

	def overlappedInterval(self, arr):
		n = len(arr)
		arr.sort()
		ans = []
		for i in range(n):
			start = arr[i][0]
			end = arr[i][1]
			if len(ans) != 0:
				if start <= ans[-1][1]:
					continue
			for j in range(i + 1, n):
				if arr[j][0] <= end:
					end = max(end, arr[j][1])
			end = max(end, arr[i][1])
			ans.append([start, end])
		return ans


class Solution:

	def overlappedInterval(self, Interval):
		Interval.sort(key=lambda i: i[0])
		st = []
		st.append(Interval[0])
		for (start, end) in Interval[1:]:
			if st[-1][1] >= start:
				st[-1][1] = max(st[-1][1], end)
			else:
				st.append([start, end])
		return st


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort(key=lambda x: x[0])
		index = 0
		for i in range(1, len(intervals)):
			if intervals[index][1] >= intervals[i][0]:
				intervals[index][1] = max(intervals[index][1], intervals[i][1])
			else:
				index = index + 1
				intervals[index] = intervals[i]
		ans = []
		for i in range(index + 1):
			ans.append(intervals[i])
		return ans


from operator import add

class Solution:

	def overlappedInterval(self, Intervals):
		i = 0
		Intervals.sort()
		ans = []
		while i < len(Intervals):
			first = Intervals[i][0]
			last = Intervals[i][1]
			while i < len(Intervals) - 1 and Intervals[i + 1][0] <= last:
				last = max(last, Intervals[i + 1][1])
				i += 1
			ans.append([first, last])
			i += 1
		return ans
		t = []
		for i in Intervals:
			t.append(i[0])
			t.append(i[1])
		ma = max(t)
		mi = min(t)
		t = []
		a = [0] * (ma + 2)
		for i in Intervals:
			a[i[0]:i[1] + 1] = list(map(add, a[i[0]:i[1] + 1], [1] * (i[1] + 1 - i[0])))
		print(a)
		s = mi
		p = 0
		for i in range(mi, ma + 1):
			if i == mi:
				p = 1
			elif a[i] == 1:
				if p == 0:
					s = i
					p = 1
			elif p == 1:
				p = 0
				t.append([s, i - 1])
			if i == ma:
				t.append([s, ma])
		return t


class Solution:

	def overlappedInterval(self, Intervals):
		sol = []
		Intervals.sort()
		s = Intervals[0][0]
		e = Intervals[0][1]
		for (l, u) in Intervals:
			if l > e:
				sol.append([s, e])
				(s, e) = (l, u)
			else:
				e = max(e, u)
		sol.append([s, e])
		return sol


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		sol = []
		start = Intervals[0][0]
		end = Intervals[0][1]
		for [l, u] in Intervals:
			if l > end:
				sol.append([start, end])
				(start, end) = (l, u)
			else:
				end = max(end, u)
		sol.append([start, end])
		return sol


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort()
		merged = [intervals[0]]
		for i in range(1, len(intervals)):
			if merged[-1][1] < intervals[i][0]:
				merged.append(intervals[i])
			elif merged[-1][1] >= intervals[i][0] and merged[-1][1] < intervals[i][1]:
				merged[-1][1] = intervals[i][1]
		return merged


class Solution:

	def overlappedInterval(self, a):
		a.sort(key=lambda x: x[0])
		ans = []
		for curr in a:
			if len(ans) == 0:
				ans.append(curr)
			else:
				prev = ans[-1]
				if prev[1] >= curr[0]:
					prev[1] = max(prev[1], curr[1])
				else:
					ans.append(curr)
		return ans


class Solution:

	def overlappedInterval(self, a):
		a.sort()
		ans = [a[0]]
		for r in a:
			if ans[-1][-1] >= r[0]:
				ans[-1][0] = min(ans[-1][0], r[0])
				ans[-1][1] = max(ans[-1][1], r[1])
			else:
				ans += [r]
		return ans


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort(key=lambda c: c[0])
		i = 0
		while i < len(Intervals):
			if i + 1 < len(Intervals) and Intervals[i][1] >= Intervals[i + 1][0]:
				if Intervals[i][1] < Intervals[i + 1][1]:
					Intervals[i][1] = Intervals[i + 1][1]
				Intervals.remove(Intervals[i + 1])
			else:
				i += 1
		return Intervals


class Solution:

	def overlappedInterval(self, intervals):
		if len(intervals) == 1:
			return intervals
		intervals.sort()
		arr = []
		minh = intervals[0][0]
		maxh = intervals[0][1]
		for i in range(n - 1):
			if intervals[i + 1][0] <= maxh:
				maxh = max(maxh, intervals[i + 1][1])
			else:
				arr.append([minh, maxh])
				minh = intervals[i + 1][0]
				maxh = intervals[i + 1][1]
		if intervals[n - 1][0] <= maxh:
			arr.append([minh, max(intervals[n - 1][1], maxh)])
		else:
			arr.append([minh, maxh])
		return arr


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort()
		stack = []
		stack.append(intervals[0])
		for i in range(1, len(intervals)):
			cst = intervals[i][0]
			cet = intervals[i][1]
			if cst <= stack[-1][1]:
				stack[-1][1] = max(stack[-1][1], cet)
			else:
				stack.append(intervals[i])
		return stack


class Solution(object):

	def overlappedInterval(self, intervals):
		intervals.sort(key=lambda x: x[0])
		stack = []
		for interval in intervals:
			(start, end) = (interval[0], interval[1])
			if not stack or stack[-1][1] < start:
				stack.append(interval)
			else:
				stack[-1][1] = max(stack[-1][1], end)
		return stack


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		m = []
		for i in range(len(Intervals)):
			if not m or m[-1][1] < Intervals[i][0]:
				m.append(Intervals[i])
			else:
				m[-1][1] = max(m[-1][1], Intervals[i][1])
		return m


class Solution:

	def overlappedInterval(self, Intervals):
		ans = []
		i = 0
		for cur in sorted(Intervals, key=lambda item: item[0]):
			if ans and ans[i - 1][1] >= cur[0]:
				ans[i - 1][1] = max(ans[i - 1][1], cur[1])
			else:
				ans.append(cur)
				i += 1
		return ans


class Solution:

	def overlappedInterval(self, arr):
		arr.sort(key=lambda x: x[0])
		index = 0
		for i in range(1, len(arr)):
			if arr[index][1] >= arr[i][0]:
				arr[index][1] = max(arr[index][1], arr[i][1])
			else:
				index = index + 1
				arr[index] = arr[i]
		return arr[:index + 1]


class Solution:

	def overlappedInterval(self, intervals):
		n = len(intervals)
		ans = []
		if n == 0:
			return []
		else:
			intervals.sort()
			left = intervals[0][0]
			right = intervals[0][1]
			for i in range(1, n):
				if intervals[i][0] <= right:
					right = max(right, intervals[i][1])
				else:
					ans += [[left, right]]
					left = intervals[i][0]
					right = intervals[i][1]
		ans += [[left, right]]
		return ans


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals = sorted(Intervals, key=lambda x: (x[0], x[1]))
		res = []
		current = Intervals[0]
		for i in range(1, len(Intervals)):
			if Intervals[i][0] <= current[1] <= Intervals[i][1] or Intervals[i][1] <= current[1]:
				current[1] = max(current[1], Intervals[i][1])
			else:
				res.append(current)
				current = Intervals[i]
		else:
			res.append(current)
		return res


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		stack = []
		for (s, e) in Intervals:
			if stack and stack[-1][1] >= s:
				(lastS, lastE) = stack.pop()
				stack.append([lastS, max(lastE, e)])
			else:
				stack.append([s, e])
		return stack


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		i = 0
		while len(Intervals) - 1 != i:
			if Intervals[i][1] >= Intervals[i + 1][0]:
				if Intervals[i][1] < Intervals[i + 1][1]:
					Intervals[i][1] = Intervals[i + 1][1]
				del Intervals[i + 1]
			else:
				i += 1
		return Intervals


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals = sorted(Intervals)
		merged = []
		for interval in Intervals:
			if not merged or merged[-1][1] < interval[0]:
				merged.append(interval)
			else:
				merged[-1][1] = max(merged[-1][1], interval[1])
		return merged


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort(key=lambda x: x[0])
		start = intervals[0][0]
		end = intervals[0][1]
		r = []
		for i in range(1, len(intervals)):
			if end >= intervals[i][0]:
				end = max(end, intervals[i][1])
			else:
				r.append([start, end])
				start = intervals[i][0]
				end = intervals[i][1]
		r.append([start, end])
		return r


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort(key=lambda x: x[0])
		answer = []
		current = Intervals[0]
		for i in range(1, len(Intervals)):
			if Intervals[i][0] <= current[1]:
				current[1] = max(current[1], Intervals[i][1])
			else:
				answer.append(current)
				current = Intervals[i]
		answer.append(current)
		return answer


class Solution:

	def overlappedInterval(self, Intervals):
		p = len(Intervals)
		if p == 1:
			return Intervals
		Intervals.sort()
		arr = []
		maxi = Intervals[0][1]
		mini = Intervals[0][0]
		for i in Intervals:
			if i[0] <= maxi:
				if maxi < i[1]:
					maxi = i[1]
			else:
				arr.append([mini, maxi])
				mini = i[0]
				maxi = i[1]
		arr.append([mini, maxi])
		return arr


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		stk = [Intervals[0][0], Intervals[0][1]]
		for i in range(1, len(Intervals)):
			if stk[-1] >= Intervals[i][0]:
				if stk[-1] < Intervals[i][1]:
					stk.pop()
					stk.append(Intervals[i][1])
			else:
				stk.append(Intervals[i][0])
				stk.append(Intervals[i][1])
		ans = []
		for i in range(0, len(stk) - 1, 2):
			ans.append([stk[i], stk[i + 1]])
		return ans


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort(key=lambda x: x[0])
		merged = []
		for i in Intervals:
			if len(merged) == 0 or merged[-1][-1] < i[0]:
				merged.append(i)
			else:
				merged[-1][-1] = max(merged[-1][-1], i[-1])
		return merged


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort()
		ans = []
		temp = intervals[0]
		for i in range(len(intervals)):
			if temp[1] < intervals[i][0]:
				ans.append(temp)
				temp = intervals[i]
			elif temp[1] >= intervals[i][0]:
				temp[1] = max(intervals[i][1], temp[1])
		ans.append(temp)
		return ans


class Solution:

	def overlappedInterval(self, arr):
		arr.sort()
		res = []
		for i in range(len(arr)):
			if not res:
				res.append(arr[i])
			elif res[-1][-1] >= arr[i][0]:
				res[-1][-1] = max(res[-1][-1], arr[i][-1])
			else:
				res.append(arr[i])
		return res


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort(key=lambda i: i[0])
		output = [intervals[0]]
		for (start, end) in intervals[1:]:
			lastEnd = output[-1][1]
			if start <= lastEnd:
				output[-1][1] = max(end, lastEnd)
			else:
				output.append([start, end])
		return output


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		if len(Intervals) == 1:
			return Intervals
		res = []
		res.append(Intervals[0])
		for interval in Intervals[1:]:
			if res[-1][0] <= interval[0] <= res[-1][1]:
				res[-1][1] = max(res[-1][1], interval[1])
			else:
				res.append(interval)
		return res


class Solution:

	def overlappedInterval(self, Intervals):
		Intervals.sort()
		res = []
		for i in Intervals:
			if res == []:
				res.append(i)
			elif i[0] > res[-1][1]:
				res.append(i)
			elif i[0] < res[-1][1]:
				if i[1] > res[-1][1]:
					res[-1][1] = i[1]
			elif i[0] == res[-1][1]:
				res[-1][1] = i[1]
		return res


class Solution:

	def overlappedInterval(self, intervals):
		intervals.sort()
		prev = intervals[0]
		ans = []
		for i in range(1, len(intervals)):
			cur = intervals[i]
			if prev[1] >= cur[0]:
				prev[1] = max(prev[1], cur[1])
			else:
				ans.append(prev)
				prev = cur
		ans.append(prev)
		return ans


class Solution:

	def overlappedInterval(self, Interval):
		n = len(Interval)
		Interval.sort(key=lambda x: x[0])
		result = []
		start = Interval[0][0]
		end = Interval[0][1]
		for i in range(1, n, 1):
			if Interval[i][0] <= end:
				end = max(end, Interval[i][1])
			else:
				result.append([start, end])
				start = Interval[i][0]
				end = Interval[i][1]
		(x, y) = Interval.pop()
		if not result or x > result[-1][1]:
			result.append([start, end])
		else:
			result[-1][1] = end
		return result