Looking at the problem, the O(N) solution is pretty straightforward, and I thought it's for sure going to TLE. Therefore I come up with an O(logN) solution.

From the problem we know:

- "start" of the intervals are sorted
- intervals are not overlapped (i.e. the end of an interval is smaller than the start of next interval, otherwise they are overlapped and should be merged into one)

from the 2 facts we can draw the following conclusion

- "end" of the intervals are also sorted

(proof: For all i, end_i > start_i > end_(i-1) => end_i > end_(i-1). "end" values are sorted)

When you have sorted integer, you can apply binary search and find the place you need to insert. You will need to do it twice: once for start of interval, once for end of interval

- start of interval: last_interval_before_insert.end < newInterval.start
- end of interval: first_interval_after_insert.start > newInterval.end

After you find the start/end of the interval, everything in between should be merged.

The general idea is like that but my code is too ugly so I don't feel like posting them :(