Facebook interview followup: how to improve if called multiple times

  • 0

    Does anyone know? can't think of any good idea as best run time is already O(log(N)). Please help, thanks!!

  • 1

    The current run time is NOT O(logn), but rather O(n), since you need to scan through the whole array.

  • 3

    If the function is called multiple times, there will be many insertions. I personally think using linked list to store the original intervals, and adding new intervals in place instead of copying all intervals would be a better solution.

  • 0

    binary search to mind the place to insert. BST (map() in C++) to find the place to insert and merge the intervals afterward.

  • 0

    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).

Log in to reply

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