## Solution

#### Approach 1: Merge Intervals

Intuition

In an interval [a, b], call b the "endpoint".

Among the given intervals, consider the interval A with the smallest endpoint. (Without loss of generality, this interval occurs in array A.)

Then, among the intervals in array B, A can only intersect one such interval in array B. (If two intervals in B intersect A, then they both share the endpoint of A -- but intervals in B are disjoint, which is a contradiction.)

Algorithm

If A has the smallest endpoint, it can only intersect B. After, we can discard A since it cannot intersect anything else.

Similarly, if B has the smallest endpoint, it can only intersect A, and we can discard B after since it cannot intersect anything else.

We use two pointers, i and j, to virtually manage "discarding" A or B repeatedly.

Complexity Analysis

• Time Complexity: , where are the lengths of A and B respectively.

• Space Complexity: , the maximum size of the answer.

Analysis written by: @awice.