Who can do this in O(N)?


  • 0
    M

    Even if the input is sorted by L, I cannot find a way without sorting again or tree structures. If you do, please help me. Thanks!

    -Mingcheng


  • 0
    A

    What makes you believe that it can be done in O(N)?


  • 0
    S

    Although I do not have a mathematically sound proof right now, you can rest assured that a worst-case O(N) solution does not exist for this problem. The best you can do is O(NlogN)


  • 0
    M

    Thank you for your answer. So the sorted array in the input is unnecessary, right?


  • 0
    S

    It depends on your algorithm. If your algo relies on 'sorting all the edges', then you have to mix up all the edges and do sorting yourself. However, if you go for a Divide and Conquer algorithm, then you need to sort buildings by L anyway, which you don't need to do again here.


Log in to reply
 

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