Oh, I see the intuition now, why it's impossible in less than O(n). Thanks!

Case : n = 4 [0, 100] [0, 99] [51, 51] [50, 50]

Answer : (51 + 51) + (0 + 100) — (0 + 0 + 51 + 50) = 101

But the optimal answer : 100 (segment 1 & 3) + 99 (segment 2 & 4) = 199

That's actual very neat. Though I didn't understand,

this implicitly force the set that supplies the pairwise min-lefts (R : rest) to be the complement of the set that supplies the pairwise max-rights (C : chosen segments). But that is not true: in a pair, the same segment can be both the min-left and the max-right.

I get the solution through above formulas. But intuitively unable to picture it.