Challenge

Given two lists of intervals, return the intersection of these two interval lists.

Example:

list1 = [[0, 2], [5,6], [24, 25]]
list2 = [[1,5],[8,13], [25, 26]]
OUTPUT = [[1,2],[5,5],[25,25]]

Solution #1 - Memory Limit Exceeded

class Solution:
    
    def interval_intersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        if not firstList or not secondList:
            return []
        max_val = max(firstList[-1][1],secondList[-1][1])
        first = [0 for i in range(0, max_val+1)]
        second = [0 for i in range(0, max_val+1)]
        for f in firstList:
            for i in range(f[0],f[1]):
                first[i] = 1
                
        for s in secondList:
            for i in range(s[0],s[1]):
                second[i] = 1
        i = 0
        output  = []
        while i < max_val + 1:
            if first[i] == second[i] == 1:
                start_index = i
                while first[i] == second[i] == 1:
                    i += 1
                else:
                    end_index = i
                output.append([start_index, end_index])
            i += 1
        i = 0 
        while i < max_val + 1:
            if first[i-1] == 0 and first[i] == 1 and second[i-1] == 1 and second[i] == 0:
                output.append([i,i])
            if second[i-1] == 0 and second[i] == 1 and first[i-1] == 1 and first[i] == 0:
                output.append([i,i])
            i += 1
        return sorted(output)

Memory inefficient because the biggest value of the two lists is used to crate first and second.

Solution #2

class Solution:

    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        if firstList is None or secondList is None:
            return []
        l_first = len(firstList)
        l_second = len(secondList)
        i = 0
        j = 0
        res = []
        while i < l_first and j < l_second:
            min_first, max_first = firstList[i][0], firstList[i][1]
            min_second, max_second = secondList[j][0], secondList[j][1]
            if min_first < min_second  < max_first:
                res.append([min_second, min(max_first, max_second)])
            if min_second < min_first < max_second:
                res.append([min_first, min(max_first, max_second)])
            if max_first == min_second:
                res.append([max_first, min_second])
            if min_first == max_second:
                res.append([max_second, max_second])
            if min_first == min_second:
                res.append([min_first, min(max_first, max_second)])
            elif min_first == min_second:
                res.append([min_first, min(max_first, max_second)])
            if max_first < max_second:
                i += 1
            else:
                j += 1
        return res

Passes all test cases.

Solution 3 - Cleaner

class Solution:
    
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        if firstList is None or secondList is None:
            return []
        l_first = len(firstList)
        l_second = len(secondList)
        i = 0
        j = 0
        res = []
        while i < l_first and j < l_second:
            low = max(firstList[i][0], secondList[j][0])
            hi = min(firstList[i][1], secondList[j][1] )
            if low <= hi:
                res.append([low, hi])
            if firstList[i][1] < secondList[j][1]:
                i += 1
            else:
                j += 1
        return res