Solutions

1. Brute Force

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        res = []
        for i in range(len(firstList)):
            startA, endA = firstList[i][0], firstList[i][1]
            for j in range(len(secondList)):
                startB, endB = secondList[j][0], secondList[j][1]
                if (startA <= startB <= endA) or (startB <= startA <= endB):
                    res.append([max(startA, startB), min(endA, endB)])
        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity:
- $O(1)$ extra space.
- $O(m + n)$ for the output list.

Where $m$ and $n$ are the sizes of the arrays $firstList$ and $secondList$ , respectively.

2. Line Sweep

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        mp = defaultdict(int)
        for s, e in firstList:
            mp[s] += 1
            mp[e + 1] -= 1
        for s, e in secondList:
            mp[s] += 1
            mp[e + 1] -= 1

        res = []
        active = 0
        prev = None
        for x in sorted(mp):
            if active == 2:
                res.append([prev, x - 1])
            active += mp[x]
            prev = x
        return res

Time & Space Complexity

Time complexity: $O((m + n) \log (m + n))$
Space complexity: $O(m + n)$

Where $m$ and $n$ are the sizes of the arrays $firstList$ and $secondList$ , respectively.

3. Two Pointers

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        res = []
        i = j = 0
        while i < len(firstList) and j < len(secondList):
            startA, endA = firstList[i]
            startB, endB = secondList[j]

            start = max(startA, startB)
            end = min(endA, endB)

            if start <= end:
                res.append([start, end])

            if endA < endB:
                i += 1
            else:
                j += 1

        return res

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity:
- $O(1)$ extra space.
- $O(m + n)$ for the output list.

Where $m$ and $n$ are the sizes of the arrays $firstList$ and $secondList$ , respectively.