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

Difficulty: interview

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
            
        # key: (Int, Int) - (first line interval id, second line interval id)
        # value: List[Int] - list of intersections
        intersections = {}
        
        def intersections_append(k: (int, int), v: int):
            #print(intersections, k, v)
            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
        #return intersections.values()


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]]:
        # if 2 events are both in started state
        state = [False, False]
        # flatten events into timestamp and flag bit, 0, 1 = A start, finish, 2, 3 = B start finish
        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
            else:
                if 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]]:
        # return self.first_implementation(A, B)
        return self.second_implementation(A, B)
    
    def first_implementation(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        \"\"\"
        Iterate over the two lists with two pointers. If the startpoint of one of the intervals is
        within the end of another then they intersect. On each operation grab the smallest interval
        start point to use as the basis for comparison.
        Time Complexity: O(m + n)
            where m/n are the sizes of the two arrays. since each element is visited at most once.
        Space Complexity: O(1) -- O(n) if taking the output into account
        \"\"\"
        intervals = []
        idx_a = idx_b = 0
        # 1. Find if the intervals intersect by seeing if the interval with the smallest start points end point overlaps with the later one
        def intervals_intersect(interval_a, interval_b):
            # test: [0,2], [1,5] => [1, 2]
            min_inter,max_inter  = (interval_a,interval_b) if interval_a[0] < interval_b[0] else (interval_b,interval_a)
            if min_inter[1] >= max_inter[0]:
                # intervals.append()
                return [max_inter[0], min(max_inter[1], min_inter[1])]
            return None
        
        # 2. iterate over the two interval lists until one of them is exhausted
        while idx_a < len(A) and idx_b < len(B):
            intersection = intervals_intersect(A[idx_a], B[idx_b])
            if intersection:
                intervals.append(intersection)
            # Need to review this discrete math concept.
            # Since all of the intervals are disjoint the smallest end point cannot be joined with another 
            # Test: A ([0,2], [5,10]) -- B ([1,5], [8,12]) produce first intersection [1,2].
            # Given that they're disjoint the next possible interval has to start after the end of the previous. 
            # since A[n][1] < B[m][1] the only next interval could be from A[n+1][0], B[m][0] since B can still encompass other from A's set.
            if A[idx_a][1] < B[idx_b][1]:
                idx_a += 1
            else:
                idx_b += 1

        return intervals
    
    def second_implementation(self,  A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        \"\"\"
        Memoized DP solution offloading the work to a helper function with a bound that returns at the first missed interval
        Time Complexity: O(m+n)
            Each combination will be visited at least once without the bounding function
            The sort at the end accounts for the O(n log n) portion.
        \"\"\"
         # 1. Find if the intervals intersect by seeing if the interval with the smallest start points end point overlaps with the later one
        def intervals_intersect(interval_a, interval_b):
            # test: [0,2], [1,5] => [1, 2]
            min_inter,max_inter  = (interval_a,interval_b) if interval_a[0] < interval_b[0] else (interval_b,interval_a)
            if min_inter[1] >= max_inter[0]:
                return [max_inter[0], min(max_inter[1], min_inter[1])]
            return None 
        
        def find_intersections(idx_a, idx_b):
            if idx_a == len(A) or idx_b == len(B):
                return []
            intervals = []
            interval_a = A[idx_a]
            interval_b = B[idx_b]
            intersection = intervals_intersect(interval_a, interval_b)
            if intersection:
                intervals.append(intersection)
            if interval_a[1] < interval_b[1]:
                idx_a+= 1
            else:
                idx_b += 1
            return intervals + find_intersections(idx_a, idx_b)

        
        return find_intersections(0, 0)
        
        
        
        

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
            
        # key: (Int, Int) - (first line interval id, second line interval id)
        # value: List[Int] - list of intersections
        #intersections = {}
    
        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):
            # Let's check if A[i] intersects B[j].
            # lo - the startpoint of the intersection
            # hi - the endpoint of the intersection
            lo = max(A[i][0], B[j][0])
            hi = min(A[i][1], B[j][1])
            if lo <= hi:
                ans.append([lo, hi])

            # Remove the interval with the smallest endpoint
            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)])
            else:
                if 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]]:
        # time O(M+N) space O(M+N)
        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])
            
            # remove interval with smallest endpoint
            if A[i][1]<B[j][1]:
                i+=1
            else:
                j+=1
        return result
#         i, j, result= 0, 0, []
#         while i<len(A) and j<len(B):
#             # find overlap or not
#             if A[i][1] < B[j][0]: 
#                 i+=1
#             elif B[j][1] < A[i][0]: 
#                 j+=1
#             else:
#                 # merged interval condition: max of start index, min of end index
#                 result.append((max(A[i][0], B[j][0]), min(A[i][1], B[j][1])))
#                 if B[j][1] <= A[i][1]:
#                     j+=1
#                 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 []
        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)
                    #if len(self.res2[-1]) > 2:
                    #    print(\"AAAAAA\")
                    #    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)
        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]:
                #intersections_append2((counter_a, counter_b), i)
                if counter_a == prev_counter_a and counter_b == prev_counter_b:
                    # append
                    res3[-1].append(i)
                else:
                    # add
                    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)))
                #tmp.sort
                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
            
        # key: (Int, Int) - (first line interval id, second line interval id)
        # value: List[Int] - list of intersections
        #intersections = {}
        
        #def intersections_append(k: (int, int), v: int):
        #    #print(intersections, k, v)
        #    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 = []
        
        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)
            #i = min(i_a, i_b)
            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
        #return intersections.values()


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

        res3 = []
        
        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]:
                #intersections_append2((counter_a, counter_b), i)
                if counter_a == prev_counter_a and counter_b == prev_counter_b:
                    # append
                    res3[-1].append(i)
                else:
                    # add
                    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]]:
        result = []
        i, j = 0, 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]]:
        
        # direct merge intervals approach
        # problem : https://leetcode.com/problems/interval-list-intersections/
        # T = O(M + N) # the lengths of A,B
        # S = O(M + N)
        
        
        ans = []
        i,j = 0,0 # two pointers to keep track of A,B
        
        while i < len(A) and j < len(B):
            
            # first the get the start pointer for the intersection
            # the start point is the fatherst away is the right one
            lo = max(A[i][0],B[j][0])
            
            # then get the pos, where the intervel ends first
            # eighter in A or B
            high = min(A[i][1],B[j][1])
            
            if lo <= high:
                ans.append([lo,high])
                
            # remove the interval with the smallest end point
            if A[i][1] < B[j][1]:
                # consider next sample in A
                i += 1
            else:
                # consider next sample in B
                j += 1
                
        return ans
        
        


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


'''
sol: Use two pointer
Time: O(M+N)
Space: O(1) -> if output is not considered else O(M+N)
'''

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):
            # Let's check if A[i] intersects B[j].
            # lo - the startpoint of the intersection
            # hi - the endpoint of the intersection
            lo = max(A[i][0], B[j][0])
            hi = min(A[i][1], B[j][1])
            if lo <= hi:
                ans.append([lo, hi])

            # Remove the interval with the smallest endpoint
            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]]:
        #they're sorted so
        #grab list from A
        #grab list from B
        
        #look for overlap
            #check 
        
        #if B ends before A, then move B along 
        #else move A along
        res = []
        a = 0
        b = 0
        while a < len(A) and b < len(B):
            #check for overlap 
            #interval from further along beginning to backmost back
            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)
        else:
            if 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]]:
        ans = []
        i = 0
        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]]:
        res = []
        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:
                res.append([low,high])
            
            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]]:
        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)
            # get rid of interval with the smallest front
            if a[1] < b[1]:
                A.pop(0)
            elif a[1] > b[1]:
                B.pop(0)
            else:
                A.pop(0) # validate
            
        # consolidate adjacent intervals in the result 
        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 len(A) == 0 or not B or len(B) == 0:
            return []
        
        res = []
        i, j, = 0, 0
        
        while i < len(A) and j < len(B):
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            
            if A[i][0] <= B[j][1] and B[j][0] <= A[i][1]:
                res.append([start, end])
            
            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]]:
        \"\"\"
        each lists are pairwise disjoint and in sorted order based on what, length? no, start!
        return the intersection of two lists
        
        [1,2], [5,5], [8,10], [15, 23], [24,24], [25, 25]
        runtime -- O(n+m)
        space comp. -- O(n+m)
        \"\"\"
        commonRegion= []
        ptr1, ptr2=0, 0
        while ptr1 <len(A) and ptr2< len(B):
            if self.isCommon(A[ptr1], B[ptr2]):
                newInterval= max(A[ptr1][0], B[ptr2][0]), min(A[ptr1][1], B[ptr2][1])
                commonRegion.append(newInterval)
            if A[ptr1][1] >= B[ptr2][1]:
                ptr2+=1
            else:
                ptr1+=1
        return commonRegion
    
    def isCommon(self, x, y):
        a, b= sorted([x, y], key= lambda x:x[0]) # sort based on starting 
        return a[1]>= b[0]

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
            # else:
            #     i+=1
            #     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):
            # check if two intervals overlap
            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])))
            # update pointers
            if A[p1][1] < B[p2][1]:
                # interval in A ends earlier
                p1 += 1
            else:
                p2 += 1
        return res


class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        res, a, b = [], 0, 0
        while a < len(A) and b < len(B):
            if A[a][1] < B[b][0]:
                a += 1
            elif B[b][1] < A[a][0]:
                b += 1
            else:
                res.append([max(A[a][0], B[b][0]), min(A[a][1], B[b][1])])
                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]]:
        ans = []
        i = j = 0

        while i < len(A) and j < len(B):
            # Let's check if A[i] intersects B[j].
            # lo - the startpoint of the intersection
            # hi - the endpoint of the intersection
            lo = max(A[i][0], B[j][0])
            hi = min(A[i][1], B[j][1])
            if lo <= hi:
                ans.append([lo, hi])

            # Remove the interval with the smallest endpoint
            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]]:
        
        output = []
        
        i, j = 0, 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:
                
                output.append([lo, hi])
                
            if A[i][1] < B[j][1]:
                
                i += 1
                
            else:
                
                j += 1
                
        return(output)


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