Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

 
Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

 
Note:

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        

Solutions:
class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		result = []
		i = j = 0
		while i < len(A) and j < len(B):
			low = max(A[i][0], B[j][0])
			high = min(A[i][1], B[j][1])
			if low <= high:
				result.append([low, high])
			if A[i][1] > B[j][1]:
				j += 1
			elif A[i][1] < B[j][1]:
				i += 1
			else:
				i += 1
				j += 1
		return result


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		ans = []
		if not A or not B:
			return ans
		cur_a = A.pop(0)
		cur_b = B.pop(0)
		while cur_a and cur_b:
			if cur_a[0] <= cur_b[1] and cur_a[1] >= cur_b[0]:
				ans.append([max(cur_a[0], cur_b[0]), min(cur_a[1], cur_b[1])])
			old_a = cur_a
			if cur_a[1] <= cur_b[1]:
				cur_a = A.pop(0) if A else None
			if old_a[1] >= cur_b[1]:
				cur_b = B.pop(0) if B else None
		return ans


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		res = []
		while A and B:
			(start1, end1) = (A[0][0], A[0][1])
			(start2, end2) = (B[0][0], B[0][1])
			if end1 <= end2:
				if start2 <= start1:
					res.append([start1, end1])
				elif start2 <= end1:
					res.append([start2, end1])
				A = A[1:]
			else:
				if start1 <= start2:
					res.append([start2, end2])
				elif start1 <= end2:
					res.append([start1, end2])
				B = B[1:]
		return res


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		extremum = [item for t in A for item in t] + [item for t in B for item in t]
		extremum.sort()
		counter_a = 0
		counter_b = 0
		next_a = A[counter_a] if A else None
		next_b = B[counter_b] if B else None
		max_a = A[-1][1] if A else None
		max_b = B[-1][1] if B else None
		intersections = {}

		def intersections_append(k: (int, int), v: int):
			if k in intersections:
				intersections[k].append(v)
				if len(intersections[k]) > 2:
					tmp = list(set(intersections[k]))
					tmp.sort()
					intersections[k] = tmp
			else:
				intersections[k] = [v]
		self.k1 = None
		self.k2 = None
		self.res2 = []

		def intersections_append2(k: (int, int), v: int):
			k1 = self.k1
			k2 = self.k2
			if k1 is not None and k2 is not None and (k[0] == k1) and (k[1] == k2):
				if self.res2:
					self.res2[-1].append(v)
					if len(self.res2[-1]) > 2:
						self.res2[-1] = sorted(set(self.res2[-1]))
				else:
					self.res2.append([v])
			else:
				self.k1 = k[0]
				self.k2 = k[1]
				self.res2.append([v])
		res = []
		for i in extremum:
			while max_a and i <= max_a and (i > next_a[1]):
				counter_a += 1
				next_a = A[counter_a] if counter_a < len(A) else None
			while max_b and i <= max_b and (i > next_b[1]):
				counter_b += 1
				next_b = B[counter_b] if counter_b < len(B) else None
			if next_a and next_b and (next_a[0] <= i <= next_a[1]) and (next_b[0] <= i <= next_b[1]):
				intersections_append((counter_a, counter_b), i)
				intersections_append2((counter_a, counter_b), i)
		return self.res2


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		time_points = list()
		for interval in A + B:
			time_points.append((interval[0], +1))
			time_points.append((interval[1] + 1, -1))
		sorted_points = sorted(time_points, key=lambda x: x[0])
		s = 0
		intersect = []
		for i in range(len(sorted_points)):
			s += sorted_points[i][1]
			if i != len(sorted_points) - 1 and sorted_points[i][0] == sorted_points[i + 1][0]:
				continue
			if s == 2:
				intersect.append((sorted_points[i][0], True))
			else:
				intersect.append((sorted_points[i][0], False))
		i = 0
		ans = list()
		while i < len(intersect):
			while not intersect[i][1]:
				i += 1
				if i == len(intersect):
					return ans
			ans.append([intersect[i][0], intersect[i + 1][0] - 1])
			i += 1
		return ans


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		state = [False, False]
		A_index = [0, 0]
		B_index = [0, 0]
		result = []

		def get_event(events, index):
			if index[0] >= len(events):
				return -1
			return events[index[0]][index[1]]
		while True:
			event_a = (get_event(A, A_index), A_index[1])
			event_b = (get_event(B, B_index), B_index[1])
			if event_a[0] < 0 or event_b[0] < 0:
				break
			event = min(event_a[0], event_b[0])
			is_already_in_progress = all(state)
			if event_a < event_b:
				if A_index[1] == 0:
					state[0] = 1
					A_index[1] = 1
				else:
					state[0] = 0
					A_index[0] += 1
					A_index[1] = 0
			elif B_index[1] == 0:
				state[1] = 1
				B_index[1] = 1
			else:
				state[1] = 0
				B_index[0] += 1
				B_index[1] = 0
			if is_already_in_progress:
				result[-1][1] = event
			elif all(state):
				result.append([event, -1])
		return result


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		result = []
		while len(A) != 0 and len(B) != 0:
			(a_start, a_end) = A[0]
			(b_start, b_end) = B[0]
			start = max(a_start, b_start)
			end = min(a_end, b_end)
			if start > end:
				if start == a_start:
					B = B[1:]
				else:
					A = A[1:]
			else:
				result.append([start, end])
				if end == a_end:
					B[0] = [start, b_end]
					A = A[1:]
				else:
					A[0] = [start, a_end]
					B = B[1:]
		return result


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		counter_a = 0
		counter_b = 0
		next_a = A[counter_a] if A else None
		next_b = B[counter_b] if B else None
		max_a = A[-1][1] if A else None
		max_b = B[-1][1] if B else None
		self.k1 = None
		self.k2 = None
		self.res2 = []

		def intersections_append2(k: (int, int), v: int):
			k1 = self.k1
			k2 = self.k2
			if k1 is not None and k2 is not None and (k[0] == k1) and (k[1] == k2):
				if self.res2:
					self.res2[-1].append(v)
					if len(self.res2[-1]) > 2:
						self.res2[-1] = sorted(set(self.res2[-1]))
				else:
					self.res2.append([v])
			else:
				self.k1 = k[0]
				self.k2 = k[1]
				self.res2.append([v])

		def get_next_items(lft_idx, rgt_idx):
			lft_idx_outer = int(lft_idx / 2)
			lft_idx_inner = lft_idx % 2
			rgt_idx_outer = int(rgt_idx / 2)
			rgt_idx_inner = rgt_idx % 2
			lft = A[lft_idx_outer][lft_idx_inner] if lft_idx_outer < len(A) else None
			rgt = B[rgt_idx_outer][rgt_idx_inner] if rgt_idx_outer < len(B) else None
			return (lft, rgt)
		u = (0, 0)
		(i_a, i_b) = get_next_items(u[0], u[1])
		while i_a is not None and i_b is not None:
			(i_a, i_b) = get_next_items(u[0], u[1])
			if i_a is not None and (i_b is None or i_a <= i_b):
				i = i_a
				u = (u[0] + 1, u[1])
			else:
				i = i_b
				u = (u[0], u[1] + 1)
			while max_a and i <= max_a and (i > next_a[1]):
				counter_a += 1
				next_a = A[counter_a] if counter_a < len(A) else None
			while max_b and i <= max_b and (i > next_b[1]):
				counter_b += 1
				next_b = B[counter_b] if counter_b < len(B) else None
			if next_a and next_b and (next_a[0] <= i <= next_a[1]) and (next_b[0] <= i <= next_b[1]):
				intersections_append2((counter_a, counter_b), i)
		return self.res2


import numpy as np

class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		ans = []
		i = j = 0
		while i < len(A) and j < len(B):
			lo = max(A[i][0], B[j][0])
			hi = min(A[i][1], B[j][1])
			if lo <= hi:
				ans.append([lo, hi])
			if A[i][1] < B[j][1]:
				i += 1
			else:
				j += 1
		return ans


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		self.k1 = None
		self.k2 = None
		self.res2 = []

		def intersections_append2(k: (int, int), v: int):
			k1 = self.k1
			k2 = self.k2
			if k1 is not None and k2 is not None and (k[0] == k1) and (k[1] == k2):
				if self.res2:
					self.res2[-1].append(v)
					if len(self.res2[-1]) > 2:
						self.res2[-1] = sorted(set(self.res2[-1]))
				else:
					self.res2.append([v])
			else:
				self.k1 = k[0]
				self.k2 = k[1]
				self.res2.append([v])

		def get_next_items(lft_idx, rgt_idx):
			lft_idx_outer = int(lft_idx / 2)
			lft_idx_inner = lft_idx % 2
			rgt_idx_outer = int(rgt_idx / 2)
			rgt_idx_inner = rgt_idx % 2
			lft = A[lft_idx_outer][lft_idx_inner] if lft_idx_outer < len(A) else None
			rgt = B[rgt_idx_outer][rgt_idx_inner] if rgt_idx_outer < len(B) else None
			lft_full = A[lft_idx_outer] if lft_idx_outer < len(A) else A[lft_idx_outer - 1]
			rgt_full = B[rgt_idx_outer] if rgt_idx_outer < len(B) else B[rgt_idx_outer - 1]
			return (lft, rgt, lft_full, rgt_full, min(lft_idx_outer, len(A) - 1), min(rgt_idx_outer, len(B) - 1))
		u = (0, 0)
		if u[0] >= len(A) or u[0] >= len(B):
			return []
		(i_a, i_b, next_a2, next_b2, counter_a, counter_b) = get_next_items(u[0], u[1])
		redo_step = True
		while not (i_a is None and i_b is None):
			if i_a is not None and i_b is None:
				(i, u) = (i_a, (u[0] + 1, u[1]))
			elif i_a is None and i_b is not None:
				(i, u) = (i_b, (u[0], u[1] + 1))
			elif i_a < i_b:
				(i, u) = (i_a, (u[0] + 1, u[1]))
			elif i_a > i_b:
				(i, u) = (i_b, (u[0], u[1] + 1))
			elif i_a == i_b and redo_step:
				(i, u) = (i_a, (u[0], u[1]))
				redo_step = False
			elif i_a == i_b and (not redo_step):
				(i, u) = (i_a, (u[0] + 1, u[1] + 1))
				redo_step = True
			if next_a2 is not None and next_b2 is not None and (next_a2[0] <= i <= next_a2[1]) and (next_b2[0] <= i <= next_b2[1]):
				intersections_append2((counter_a, counter_b), i)
			(i_a, i_b, next_a2, next_b2, counter_a, counter_b) = get_next_items(u[0], u[1])
		return self.res2


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		NA = len(A)
		NB = len(B)
		if NA == 0 or NB == 0:
			return []
		pA = 0
		pB = 0
		res = []
		while pA < NA and pB < NB:
			sA = A[pA][0]
			eA = A[pA][1]
			sB = B[pB][0]
			eB = B[pB][1]
			if sA <= sB:
				if eA >= sB:
					res.append([sB, min(eA, eB)])
			elif eB >= sA:
				res.append([sA, min(eA, eB)])
			if eA < eB:
				pA += 1
			elif eA == eB:
				pA += 1
				pB += 1
			else:
				pB += 1
		return res


import numpy as np

class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		res = []
		i = j = 0
		while i < len(A) and j < len(B):
			left = max(A[i][0], B[j][0])
			right = min(A[i][1], B[j][1])
			if left <= right:
				res.append([left, right])
			if A[i][1] < B[j][1]:
				i += 1
			else:
				j += 1
		return res


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		result = []
		i = j = 0
		while i < len(A) and j < len(B):
			lo = max(A[i][0], B[j][0])
			hi = min(A[i][1], B[j][1])
			if lo <= hi:
				result.append([lo, hi])
			if A[i][1] < B[j][1]:
				i += 1
			else:
				j += 1
		return result


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		if not A or not B:
			return []
		res = []
		i = j = 0
		while i < len(A) and j < len(B):
			(s, e) = (max(A[i][0], B[j][0]), min(A[i][1], B[j][1]))
			if s <= e:
				res.append([s, e])
			if A[i][1] < B[j][1]:
				i += 1
			else:
				j += 1
		return res


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		res3 = []
		self.k1 = None
		self.k2 = None
		self.res2 = []

		def intersections_append2(k: (int, int), v: int):
			k1 = self.k1
			k2 = self.k2
			if k1 is not None and k2 is not None and (k[0] == k1) and (k[1] == k2):
				if self.res2:
					self.res2[-1].append(v)
				else:
					self.res2.append([v])
			else:
				self.k1 = k[0]
				self.k2 = k[1]
				self.res2.append([v])

		def get_next_items(lft_idx, rgt_idx):
			lft_idx_outer = int(lft_idx / 2)
			lft_idx_inner = lft_idx % 2
			rgt_idx_outer = int(rgt_idx / 2)
			rgt_idx_inner = rgt_idx % 2
			lft = A[lft_idx_outer][lft_idx_inner] if lft_idx_outer < len(A) else None
			rgt = B[rgt_idx_outer][rgt_idx_inner] if rgt_idx_outer < len(B) else None
			lft_full = A[lft_idx_outer] if lft_idx_outer < len(A) else A[lft_idx_outer - 1]
			rgt_full = B[rgt_idx_outer] if rgt_idx_outer < len(B) else B[rgt_idx_outer - 1]
			return (lft, rgt, lft_full, rgt_full, min(lft_idx_outer, len(A) - 1), min(rgt_idx_outer, len(B) - 1))
		u = (0, 0)
		a_idx = 0
		b_idx = 0
		if a_idx >= len(A) or b_idx >= len(B):
			return []
		prev_counter_a = None
		prev_counter_b = None
		(i_a, i_b, next_a2, next_b2, counter_a, counter_b) = get_next_items(a_idx, b_idx)
		redo_step = True
		while not (i_a is None and i_b is None):
			if i_a is not None and i_b is None:
				a_idx += 1
			elif i_a is None and i_b is not None:
				b_idx += 1
			elif i_a < i_b:
				a_idx += 1
			elif i_a > i_b:
				b_idx += 1
			elif i_a == i_b and redo_step:
				redo_step = False
			elif i_a == i_b and (not redo_step):
				a_idx += 1
				b_idx += 1
				redo_step = True
			i = min((k for k in [i_a, i_b] if k is not None))
			if next_a2 is not None and next_b2 is not None and (next_a2[0] <= i <= next_a2[1]) and (next_b2[0] <= i <= next_b2[1]):
				if counter_a == prev_counter_a and counter_b == prev_counter_b:
					res3[-1].append(i)
				else:
					res3.append([i])
				prev_counter_a = counter_a
				prev_counter_b = counter_b
			(i_a, i_b, next_a2, next_b2, counter_a, counter_b) = get_next_items(a_idx, b_idx)
		res4 = []
		for x in res3:
			if len(x) > 2:
				tmp = sorted(list(set(x)))
				res4.append(tmp)
			else:
				res4.append(x)
		return res4


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		extremum = [item for t in A for item in t] + [item for t in B for item in t]
		extremum.sort()
		counter_a = 0
		counter_b = 0
		next_a = A[counter_a] if A else None
		next_b = B[counter_b] if B else None
		max_a = A[-1][1] if A else None
		max_b = B[-1][1] if B else None
		self.k1 = None
		self.k2 = None
		self.res2 = []

		def intersections_append2(k: (int, int), v: int):
			k1 = self.k1
			k2 = self.k2
			if k1 is not None and k2 is not None and (k[0] == k1) and (k[1] == k2):
				if self.res2:
					self.res2[-1].append(v)
					if len(self.res2[-1]) > 2:
						self.res2[-1] = sorted(set(self.res2[-1]))
				else:
					self.res2.append([v])
			else:
				self.k1 = k[0]
				self.k2 = k[1]
				self.res2.append([v])

		def get_next_items(idx_pair):
			lft_idx_outer = int(idx_pair[0] / 2)
			lft_idx_inner = idx_pair[0] % 2
			rgt_idx_outer = int(idx_pair[1] / 2)
			rgt_idx_inner = idx_pair[1] % 2
			lft = A[lft_idx_outer][lft_idx_inner] if lft_idx_outer < len(A) else None
			rgt = B[rgt_idx_outer][rgt_idx_inner] if rgt_idx_outer < len(B) else None
			return (lft, rgt)
		u = (0, 0)
		(i_a, i_b) = get_next_items(u)
		print((i_a, i_b))
		while i_a is not None and i_b is not None:
			print((i_a, i_b))
			(i_a, i_b) = get_next_items(u)
			if i_a is not None and (i_b is None or i_a <= i_b):
				i = i_a
				u = (u[0] + 1, u[1])
			else:
				i = i_b
				u = (u[0], u[1] + 1)
			while max_a and i <= max_a and (i > next_a[1]):
				counter_a += 1
				next_a = A[counter_a] if counter_a < len(A) else None
			while max_b and i <= max_b and (i > next_b[1]):
				counter_b += 1
				next_b = B[counter_b] if counter_b < len(B) else None
			if next_a and next_b and (next_a[0] <= i <= next_a[1]) and (next_b[0] <= i <= next_b[1]):
				intersections_append2((counter_a, counter_b), i)
		return self.res2


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		res = []
		a = 0
		b = 0
		while a < len(A) and b < len(B):
			start = max(A[a][0], B[b][0])
			end = min(A[a][1], B[b][1])
			if start <= end:
				res.append([start, end])
			if A[a][1] < B[b][1]:
				a += 1
			else:
				b += 1
		return res


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		(i, j, ans) = (0, 0, [])
		while i < len(A) and j < len(B):
			(a, b) = (A[i], B[j])
			if not (a[1] < b[0] or a[0] > b[1]):
				ans.append([max(a[0], b[0]), min(a[1], b[1])])
			if a[1] >= b[1]:
				j += 1
			elif b[1] >= a[1]:
				i += 1
		return ans


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		(i, j) = (0, 0)
		res = []
		A.append([math.inf, math.inf])
		B.append([math.inf, math.inf])
		while i < len(A) - 1 or j < len(B) - 1:
			((i1_s, i1_e), (i2_s, i2_e)) = (A[i], B[j])
			if i1_e >= i2_s:
				if i1_s <= i2_e:
					res.append([max(i1_s, i2_s), min(i1_e, i2_e)])
				j += 1
			else:
				if j > 0:
					j -= 1
				i += 1
		return res


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		if not A or not B:
			return []
		(m, n) = (len(A), len(B))
		result = []
		i = j = 0
		while i < m and j < n:
			start = max(A[i][0], B[j][0])
			end = min(A[i][1], B[j][1])
			if start <= end:
				result.append([start, end])
			if A[i][1] < B[j][1]:
				i += 1
			else:
				j += 1
		return result


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		i = 0
		j = 0
		ans = []
		while i < len(A) and j < len(B):
			if A[i][0] >= B[j][0] and A[i][1] <= B[j][1]:
				ans.append([A[i][0], A[i][1]])
				i += 1
			elif B[j][0] >= A[i][0] and B[j][1] <= A[i][1]:
				ans.append([B[j][0], B[j][1]])
				j += 1
			elif A[i][1] >= B[j][0] and A[i][0] <= B[j][0]:
				ans.append([B[j][0], A[i][1]])
				i += 1
			elif B[j][1] >= A[i][0] and B[j][0] <= A[i][0]:
				ans.append([A[i][0], B[j][1]])
				j += 1
			elif B[j][1] < A[i][0]:
				j += 1
			elif A[i][1] < B[j][0]:
				i += 1
		return ans


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		if len(A) == 0 or len(B) == 0:
			return []
		(a_start, a_end) = A[0]
		(b_start, b_end) = B[0]
		start = max(a_start, b_start)
		end = min(a_end, b_end)
		if start > end:
			if start == a_start:
				return self.intervalIntersection(A, B[1:])
			else:
				return self.intervalIntersection(A[1:], B)
		elif end == a_end:
			B[0] = [start, b_end]
			return [[start, end]] + self.intervalIntersection(A[1:], B)
		else:
			A[0] = [start, a_end]
			return [[start, end]] + self.intervalIntersection(A, B[1:])


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		if not A or not B:
			return []
		ans = []
		i = j = 0
		while i < len(A) and j < len(B):
			lo = max(A[i][0], B[j][0])
			hi = min(A[i][1], B[j][1])
			if lo <= hi:
				ans.append([lo, hi])
			if B[j][1] > A[i][1]:
				i += 1
			elif B[j][1] < A[i][1]:
				j += 1
			else:
				i += 1
				j += 1
		return ans


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		intervals = deque()
		while A and B:
			(a, b) = (A[-1], B[-1])
			(x, y) = (max(a[0], b[0]), min(a[1], b[1]))
			if x <= y:
				intervals.appendleft([x, y])
			(A if a > b else B).pop()
		return intervals


class Solution:

	def overlap(self, lst):
		lst.sort(key=lambda x: x[0])
		if lst[0][1] >= lst[1][0]:
			return True
		return False

	def add_data(self, start_a, end_a, start_b, end_b, res):
		if self.overlap([(start_a, end_a), (start_b, end_b)]):
			(start, end) = (max(start_a, start_b), min(end_a, end_b))
			if (start, end) not in res:
				res.append((start, end))
		return res

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		if not A or not B:
			return []
		(start_a, end_a) = A.pop(0)
		(start_b, end_b) = B.pop(0)
		res = []
		while A and B:
			res = self.add_data(start_a, end_a, start_b, end_b, res)
			if end_a < end_b:
				(start_a, end_a) = A.pop(0)
			else:
				(start_b, end_b) = B.pop(0)
		while A:
			res = self.add_data(start_a, end_a, start_b, end_b, res)
			(start_a, end_a) = A.pop(0)
		while B:
			res = self.add_data(start_a, end_a, start_b, end_b, res)
			(start_b, end_b) = B.pop(0)
		res = self.add_data(start_a, end_a, start_b, end_b, res)
		return res


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		ite1 = 0
		ite2 = 0
		lenA = len(A)
		lenB = len(B)
		ans = []
		while ite1 < lenA and ite2 < lenB:
			curA = A[ite1]
			curB = B[ite2]
			(s, e) = (max(curA[0], curB[0]), min(curA[1], curB[1]))
			if s <= e:
				ans.append([s, e])
			if curA[1] > curB[1]:
				ite2 += 1
			elif curA[1] < curB[1]:
				ite1 += 1
			else:
				ite1 += 1
				ite2 += 1
		return ans


def intersection(a: List, b: List) -> List:
	l = max(a[0], b[0])
	r = min(a[1], b[1])
	if l <= r:
		return [l, r]
	else:
		return None

def union(a: List, b: List) -> List:
	l = min(a[0], b[0])
	r = max(a[1], b[1])
	i = intersection(a, b)
	if i:
		return [l, r]
	else:
		return None

class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		result = []
		while A and B:
			a = A[0]
			b = B[0]
			i = intersection(a, b)
			if i:
				result.append(i)
			if a[1] < b[1]:
				A.pop(0)
			elif a[1] > b[1]:
				B.pop(0)
			else:
				A.pop(0)
		i = 1
		while i < len(result):
			u = union(result[i - 1], result[i])
			if u:
				result.pop(i - 1)
				result.pop(i - 1)
				result.insert(i - 1, u)
			else:
				i += 1
		return result


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		if not A or not B:
			return []
		MergedList = A + B
		MergedList.sort()
		result = []
		for i in range(len(MergedList)):
			if i == 0:
				continue
			if MergedList[i][0] <= MergedList[i - 1][1]:
				result.append([max(MergedList[i - 1][0], MergedList[i][0]), min(MergedList[i - 1][1], MergedList[i][1])])
				MergedList[i][1] = max(MergedList[i - 1][1], MergedList[i][1])
		return result


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		ans = []
		i = j = 0
		while i < len(A) and j < len(B):
			l = max(A[i][0], B[j][0])
			h = min(A[i][1], B[j][1])
			if l <= h:
				ans.append([l, h])
			if A[i][1] < B[j][1]:
				i += 1
			else:
				j += 1
		return ans


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		(p1, p2) = (0, 0)
		res = []
		while p1 < len(A) and p2 < len(B):
			if not (B[p2][1] < A[p1][0] or A[p1][1] < B[p2][0]):
				res.append((max(A[p1][0], B[p2][0]), min(A[p1][1], B[p2][1])))
			if A[p1][1] < B[p2][1]:
				p1 += 1
			else:
				p2 += 1
		return res


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		i = 0
		j = 0
		result = []
		while i < len(A) and j < len(B):
			if self.overlap(A[i], B[j]):
				result.append(self.intersection(A[i], B[j]))
			if A[i][1] <= B[j][1]:
				i += 1
			else:
				j += 1
		return result

	def overlap(self, i1, i2):
		return any([i1[0] <= i2[0] <= i1[1], i1[0] <= i2[1] <= i1[1], i2[0] <= i1[0] <= i2[1], i2[0] <= i1[1] <= i2[1]])

	def intersection(self, i1, i2):
		return [max(i1[0], i2[0]), min(i1[1], i2[1])]


class Solution:

	def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
		res3 = []
		a_idx = 0
		b_idx = 0
		if a_idx >= len(A) or b_idx >= len(B):
			return []
		redo_step = False
		while a_idx < len(A) and b_idx < len(B):
			next_a2 = A[a_idx]
			next_b2 = B[b_idx]
			i_a = next_a2[0]
			i_b = next_b2[0]
			if next_a2[1] < next_b2[1]:
				a_idx += 1
			else:
				b_idx += 1
			max_lft = max((k for k in [next_a2[0], next_b2[0]]))
			min_rgt = min((k for k in [next_a2[1], next_b2[1]]))
			if max_lft <= min_rgt:
				res3.append([max_lft, min_rgt])
		return res3