Good thinking.
But, the solution is O(n) and not O(log n). Consider the following example:
[[2,3],[5,7],[9,11],[12,15]]
[1,16]
In this case you insert [1,16] at the end of the list and remove all the n elements in the list.
Good thinking.
But, the solution is O(n) and not O(log n). Consider the following example:
[[2,3],[5,7],[9,11],[12,15]]
[1,16]
In this case you insert [1,16] at the end of the list and remove all the n elements in the list.
I was thinking of another approach that is not mentioned here yet. Put everything into a priority queue(I understand that the input is already in sorted order). Do the bunch of inserts(really a huge number). This is to make sure after all the inserts the values are still in sorted order.
Then just go ahead and perform the merge in the end. This way the worst case complexity will be O(n logn).