2 ms·
If you think recursively, the n log n divide and conquer solution is pretty straightforward. The problem becomes much more interesting when you consider optima
by sgeisenh 12y ago
If you think recursively, the n log n divide and conquer solution is pretty straightforward.
The problem becomes much more interesting when you consider optimal parallel performance. The best span you can do is log^2 n. I believe the problem can be reduced to sorting, though it is not required to explicitly sort the sequence of buildings in order to achieve the desired asymptotic performance.
- cperciva 12y agoI believe the problem can be reduced to sorting Speaking of which: Given values 0 < a_i < A for some A, apply the skyline algorithm to the rectangles a_i < x < A, 0 < y < a_i. The resulting sequence of heights gives you the values a_i sorted in increasing order; thus the skyline problem cannot be solved in less than O(n log n) time.