Geek has an array of N non-overlapping intervals intervals where intervals[i] = [start_{i}, end_{i}] represent the start and the end of the i^{th} event and intervals is sorted in ascending order by start_{i}. He wants to add a new interval newEvent = [newStart, newEnd] where newStart and newEnd represent the start and end of this interval.
Help Geek to insert newEvent into intervals such that intervals is still sorted in ascending order by start_{i} and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Example 1:
Input:
N = 3
intervals = [[1,3], [10,15], [20,30]]
newEvent  = [5,6]
Output: [[1,3], [5,6], [10,15], [20,30]]
Explanation: The newEvent (5, 6) does not overlap with any of the existing ranges, hence it is added 
to the intervals list maintaining the sorted order of start times.
Example 2:
Input:
N = 5
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newEvent  = [5,10]
Output: [[1,2], [3,10], [12,16]]
Explanation: Because the new interval [5,10] overlaps with [3,5],[6,7],[8,10].
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function insertNewEvent() which takes N, the list of intervals and newEvent as input and returns the final list of intervals after inserting the newEvent in the original list.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤  10^{4}
0 ≤ start[i], end[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def insertNewEvent(self, N, intervals, newEvent):

        # Code here

Solutions:
class Solution:

	def isIntervals(self, a, b):
		if a[0] > b[1] or a[1] < b[0]:
			return False
		return True

	def insertNewEvent(self, N, intervals, newEvent):
		if N == 0:
			return [newEvent]
		ans = []
		used = 0
		for c in intervals:
			if used == 0 and newEvent < c:
				used = 1
				while len(ans) > 0 and self.isIntervals(ans[-1], newEvent):
					prev = ans.pop()
					newEvent = [min(prev[0], newEvent[0]), max(prev[1], newEvent[1])]
				ans.append(newEvent)
			while len(ans) > 0 and self.isIntervals(ans[-1], c):
				prev = ans.pop()
				c = [min(prev[0], c[0]), max(prev[1], c[1])]
				if used == 0 and self.isIntervals(c, newEvent):
					used = 1
					c = [min(newEvent[0], c[0]), max(newEvent[1], c[1])]
			ans.append(c)
		if used == 0:
			while len(ans) > 0 and self.isIntervals(ans[-1], newEvent):
				prev = ans.pop()
				newEvent = [min(prev[0], newEvent[0]), max(prev[1], newEvent[1])]
			ans.append(newEvent)
		return ans


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):

		def getinsertpos(intervals, newEvent):
			(low, high) = (0, len(intervals))
			while low < high:
				mid = (low + high) // 2
				if intervals[mid][0] < newEvent[0]:
					low = mid + 1
				else:
					high = mid
			return low
		insert_pos = getinsertpos(intervals, newEvent)
		intervals.insert(insert_pos, newEvent)
		curr_interval = intervals[0]
		res = []
		for i in range(1, len(intervals)):
			if intervals[i][0] <= curr_interval[1] <= intervals[i][1] or curr_interval[1] > intervals[i][1]:
				curr_interval[1] = max(curr_interval[1], intervals[i][1])
			else:
				res.append(curr_interval)
				curr_interval = intervals[i]
		res.append(curr_interval)
		return res


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):
		n1 = len(intervals)
		ind = 0
		if not intervals:
			intervals.append(newEvent)
			return intervals
		if len(intervals) == 1:
			if intervals[0][1] < newEvent[0]:
				intervals.insert(1, newEvent)
				return intervals
			elif newEvent[1] < intervals[0][0]:
				intervals.insert(0, newEvent)
				return intervals
		for i in range(n1):
			if newEvent[1] < intervals[i][0]:
				intervals.insert(i, newEvent)
				return intervals
			if newEvent[0] <= intervals[i][1]:
				intervals[i][1] = max(intervals[i][1], newEvent[1])
				intervals[i][0] = min(newEvent[0], intervals[i][0])
				x = intervals[i][1]
				ind = i
				break
		if newEvent[0] > intervals[-1][1]:
			intervals.append(newEvent)
			return intervals
		j = ind + 1
		while j < n1:
			if x >= intervals[j][0]:
				intervals[j - 1][1] = max(intervals[j - 1][1], intervals[j][1])
				x = intervals[j - 1][1]
				intervals.pop(j)
			elif intervals[j - 1][1] < intervals[j][0]:
				break
			else:
				j += 1
			n1 = len(intervals)
		return intervals


class Solution:

	def leftMerge(intervals, index):
		if index == 0 or index >= len(intervals):
			return intervals
		if intervals[index][0] <= intervals[index - 1][1]:
			intervals[index - 1][1] = max(intervals[index][1], intervals[index - 1][1])
			del intervals[index]
			Solution.leftMerge(intervals, index)
		else:
			return intervals

	def insertNewEvent(self, N, intervals, newInterval):
		insertIndex = len(intervals)
		for (index, interval) in enumerate(intervals):
			if interval[0] >= newInterval[0]:
				insertIndex = index
				break
		intervals.insert(insertIndex, newInterval)
		Solution.leftMerge(intervals, insertIndex)
		Solution.leftMerge(intervals, insertIndex + 1)
		return intervals


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):
		ans = []
		i = 0
		while i < N and newEvent[0] > intervals[i][1]:
			ans.append(intervals[i])
			i += 1
		while i < N and newEvent[1] >= intervals[i][0]:
			newEvent[0] = min(intervals[i][0], newEvent[0])
			newEvent[1] = max(intervals[i][1], newEvent[1])
			i += 1
		ans.append(newEvent)
		while i < N:
			ans.append(intervals[i])
			i += 1
		return ans


class Solution:

	def insertNewEvent(self, N, intervals, newInterval):
		intervals.append(newInterval)
		intervals.sort()
		merged = [intervals[0]]
		for i in range(1, N + 1):
			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 insertNewEvent(self, N, intervals, newEvent):
		res = []
		for i in range(len(intervals)):
			if newEvent[1] < intervals[i][0]:
				res.append(newEvent)
				return res + intervals[i:]
			elif newEvent[0] > intervals[i][1]:
				res.append(intervals[i])
			else:
				newEvent = [min(newEvent[0], intervals[i][0]), max(newEvent[1], intervals[i][1])]
		res.append(newEvent)
		return res


class Solution:

	def insertNewEvent(self, N, intervals, newInterval):
		from bisect import bisect_left
		insertI = bisect_left(intervals, newInterval)
		intervals.insert(insertI, newInterval)
		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 insertNewEvent(self, N, intervals, newEvent):
		intervals.append(newEvent)
		intervals.sort(key=lambda x: x[0])
		s = intervals[0][0]
		e = intervals[0][1]
		r = []
		for i in range(1, len(intervals)):
			if e >= intervals[i][0]:
				e = max(e, intervals[i][1])
			else:
				r.append([s, e])
				s = intervals[i][0]
				e = intervals[i][1]
		r.append([s, e])
		return r


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):
		inserted = False
		n = len(intervals)
		for i in range(n):
			if newEvent[0] >= intervals[i][0]:
				continue
			inserted = True
			intervals.insert(i, newEvent)
			break
		if inserted == False:
			intervals.append(newEvent)
		newarr = []
		if len(intervals) == 1:
			return intervals
		last = intervals[0]
		for i in range(1, len(intervals)):
			if intervals[i][0] <= last[1]:
				last = [last[0], max(last[1], intervals[i][1])]
				i += 1
			else:
				newarr.append(last)
				last = intervals[i]
				i += 1
		newarr.append(last)
		intervals = newarr
		return intervals


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):
		intervals.sort()
		ans = []
		ind = 0
		intervals.append(newEvent)
		intervals.sort()
		s = intervals[0][0]
		e = intervals[0][1]
		for (i, j) in intervals:
			if i <= e:
				e = max(e, j)
			else:
				ans.append([s, e])
				s = i
				e = j
		ans.append([s, e])
		return ans


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):
		intervals.append(newEvent)
		intervals.sort()
		(s, e) = (intervals[0][0], intervals[0][1])
		ans = []
		for i in range(1, len(intervals)):
			if e >= intervals[i][0]:
				e = max(e, intervals[i][1])
			else:
				ans.append([s, e])
				s = intervals[i][0]
				e = intervals[i][1]
		ans.append([s, e])
		return ans


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):
		intervals.append(newEvent)
		stack = []
		intervals.sort(key=lambda x: x[0])
		stack.append(intervals[0])
		for i in range(1, len(intervals)):
			if intervals[i][0] <= stack[-1][1]:
				a = stack.pop(-1)
				stack.append([a[0], max(a[1], intervals[i][1])])
			else:
				stack.append(intervals[i])
		return stack


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):
		(m, n) = (newEvent[0], newEvent[1])
		res = []
		for i in range(N):
			(a, b) = (intervals[i][0], intervals[i][1])
			if b < m:
				res.append([a, b])
			elif a > n:
				if [m, n] not in res:
					res.append([m, n])
				res = res + intervals[i:]
				break
			elif a <= m or b <= m:
				res.append([a, max(b, n)])
				m = a
				n = max(b, n)
			elif a <= n and b <= n:
				if [min(a, m), n] not in res:
					res.append([min(a, m), n])
			elif a <= n and b > n:
				if [m, n] not in res:
					res.append([m, n])
				res.pop()
				res.append([m, b])
				n = b
		if b < m:
			res.append([m, n])
		return res


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):
		i = 0
		ans = []
		while i < len(intervals):
			if newEvent[1] < intervals[i][0]:
				ans.append(newEvent)
				return ans + intervals[i:]
			elif newEvent[0] > intervals[i][1]:
				ans.append(intervals[i])
			else:
				newEvent = [min(newEvent[0], intervals[i][0]), max(newEvent[1], intervals[i][1])]
			i += 1
		ans.append(newEvent)
		return ans


class Solution:

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


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):
		pos = 0
		flag = 0
		for i in range(N):
			if intervals[i][0] > newEvent[0]:
				pos = i
				flag = 1
				intervals.insert(i, newEvent)
				break
		if flag == 0:
			pos = N
			intervals.insert(N, newEvent)
		if pos > 0:
			if intervals[pos][0] <= intervals[pos - 1][1]:
				a = [intervals[pos - 1][0], max(intervals[pos - 1][1], intervals[pos][1])]
				intervals.pop(pos)
				intervals.pop(pos - 1)
				intervals.insert(pos - 1, a)
				pos = pos - 1
		i = pos
		while i < len(intervals) and intervals[pos][1] >= intervals[i][0]:
			i += 1
		i -= 1
		a = [intervals[pos][0], max(intervals[pos][1], intervals[i][1])]
		intervals.insert(i + 1, a)
		for j in range(pos, i + 1):
			intervals.pop(pos)
		return intervals


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):

		def binarySearch():
			left = 0
			right = len(intervals) - 1
			while left <= right:
				mid = left + right >> 1
				if intervals[mid][0] <= newEvent[0]:
					left = mid + 1
				else:
					right = mid - 1
			return left
		index = binarySearch()
		if index == N:
			intervals.append([newEvent[0], newEvent[1]])
		else:
			intervals = intervals[:index] + [[newEvent[0], newEvent[1]]] + intervals[index:]

		def MergeOverlappingIntervals(intervals):
			result = [intervals[0]]
			for lst in intervals[1:]:
				if result[-1][-1] < lst[0]:
					result.append(lst)
				else:
					result[-1][-1] = max(result[-1][-1], lst[-1])
			return result
		return MergeOverlappingIntervals(intervals)


class Solution:

	def insertNewEvent(self, N, intervals, newInterval):
		res = []
		i = 0
		n = len(intervals)
		while i < n and intervals[i][1] < newInterval[0]:
			res.append(intervals[i])
			i += 1
		while i < n and intervals[i][0] <= newInterval[1]:
			newInterval[0] = min(intervals[i][0], newInterval[0])
			newInterval[1] = max(intervals[i][1], newInterval[1])
			i += 1
		res.append(newInterval)
		while i < n:
			res.append(intervals[i])
			i += 1
		return res


class Solution:

	def insertNewEvent(self, n, arr, event):
		arr.append(event)
		arr.sort()
		n += 1
		i = 0
		j = 1
		ans = []
		while i < n - 1:
			while j < n and arr[i][1] >= arr[j][0]:
				arr[i][1] = max(arr[i][1], arr[j][1])
				j += 1
			ans.append(arr[i])
			i = j
			j += 1
		if i == n - 1:
			ans.append(arr[i])
		return ans


class Solution:

	def insertNewEvent(self, N, intervals, newEvent):
		for ind in range(len(intervals)):
			if intervals[ind][1] > newEvent[0]:
				break
		intervals.insert(ind, newEvent)
		intervals = sorted(intervals, key=lambda x: x[0])
		q = [intervals[0]]
		for i in range(1, len(intervals)):
			if q[-1][1] >= intervals[i][0]:
				(a, b) = q.pop()
				q.append([a, max(b, intervals[i][1])])
			else:
				q.append(intervals[i])
		return q


class Solution:

	def overlappedInterval(self, arr):
		start = arr[0][0]
		end = arr[0][1]
		ans = []
		for lst in arr[1:]:
			i = lst[0]
			j = lst[1]
			if i <= end:
				end = max(end, j)
			else:
				ans.append([start, end])
				start = i
				end = j
		ans.append([start, end])
		return ans

	def insertNewEvent(self, N, intervals, newEvent):
		for i in range(N):
			if intervals[i][0] >= newEvent[0]:
				intervals.insert(i, newEvent)
				break
		intervals.append(newEvent)
		return self.overlappedInterval(intervals)