Merging Intervals

Suppose an interval is completely contained in another interval. For any third interval, replacing the contained interval by the containing interval cannot decrease the length of the union. Therefore, contained intervals can be removed when searching for an optimum.

Sort the intervals by increasing $l$, and for equal $l$ by decreasing $r$. Scan from left to right and remove every interval whose $r$ is not larger than the maximum $r$ seen so far. Let the remaining intervals be

$$[l_1,r_1],[l_2,r_2],\cdots,[l_M,r_M].$$

Then

$$l_1<l_2<\cdots<l_M,\qquad r_1<r_2<\cdots<r_M.$$

Initialize the answer with the maximum length of any original interval. This also handles the case where every other interval is contained in one interval.

Now fix the right interval $j$. Maintain with a two-pointer scan the boundary between earlier intervals satisfying $r_i<l_j$ and those satisfying $r_i\geq l_j$.

If $r_i<l_j$, interval $i$ is disjoint from interval $j$, so the union length is

$$(r_i-l_i)+(r_j-l_j).$$

With a prefix maximum of interval lengths, the best value of this form is available immediately.

If $r_i\geq l_j$, the two intervals overlap or touch. Since the right endpoints of the remaining intervals are strictly increasing, $r_i<r_j$, so their union is

$$[l_i,r_j].$$

Thus, among all such $i$, the best choice is the earliest one, which has the smallest $l_i$.

Sorting takes $O(N\log N)$ time, and the filtering, prefix preprocessing, and two-pointer scan take $O(N)$ time. The total time complexity is $O(N\log N)$.

Every interval lies inside $[0,10^9]$, so the union of any two intervals also lies inside this range. Therefore, the answer is at most $10^9$ and always fits in a signed 64-bit integer.

Solution written by GPT5.6