Key insight is that it is much easier and more efficient to merge if we sort the ranges by the range begin. That results in O(nlogn) solution and I don’t think it can be done quicker than that.

Key insight is that it is much easier and more efficient to merge if we sort the ranges by the range begin. That results in O(nlogn) solution and I don’t think it can be done quicker than that.