Your browser does not seem to support JavaScript. As a result, your viewing experience will be diminished, and you have been placed in read-only mode.

Please download a browser that supports JavaScript, or enable it if it's disabled (i.e. NoScript).

sorted is meaningless. Given a random non-overlapping list, we can insert in O(n)sdffsf

However given sorted intervals, we could do the insertion in O(log n) time and O(1) space.

you can locate where to insert in logn, but the insertion to an array is linear.

How to do it in O(n) if it is not sorted?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.