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)

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.