Interval Intersections - Algorithm

Use two pointers, one for each list. For current intervals A[i] and B[j]:

$1.$ Compute intersection: [max(A[i].start, B[j].start), min(A[i].end, B[j].end)].

$2.$ If start <= end, add to result.

$3.$ Move the pointer of the interval that ends earlier (it cannot intersect any more intervals in the other list). It works because both lists are sorted. Time: $O(n + m)$. Space: $O(k)$ for $k$ intersections.