Problem statement

https://leetcode.com/problems/interval-list-intersections/

Solution

Intervals are already sorted, so what we can do is use two pointers technique: take intervals i and j and try to create intersection. If it is not empty, add it to answer. Then we decide, which interval to choose next, we move the one which ends earlier (if we move the one which starts earlier, we can loose some parts, draw some examples and make sure).

Complexity

It is O(n + m) for time and space.

Code

class Solution:
    def intervalIntersection(self, A, B):
        i, j, ans = 0, 0, []
        while i < len(A) and j < len(B):
            curr = [max(A[i][0], B[j][0]), min(A[i][1], B[j][1])]
            if curr[0] <= curr[1]:
                ans += [curr]
            if A[i][1] <= B[j][1]:
                i += 1
            else:
                j += 1

        return ans