Approach 1: Merge Intervals
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
Then, among the intervals in array
A can only intersect one such interval in array
B. (If two intervals in
A, then they both share the endpoint of
A -- but intervals in
B are disjoint, which is a contradiction.)
A has the smallest endpoint, it can only intersect
B. After, we can discard
A since it cannot intersect anything else.
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,
j, to virtually manage "discarding"
Time Complexity: , where are the lengths of
Space Complexity: , the maximum size of the answer.
Analysis written by: @awice.