I implement an iterative solution of 16.14, and want to share with others.
The basic idea: to get the sky line at a specific point, we should get the biggest height of all the building at this point. So if we have a list of buildings whose range covers this point, we can get the highest building, and we can move the point from left to right. When we meet a new building, we add the building to the list, for we leave the range of a building, we remove the building from the list. You may notice, the height of sky line will only change when we meet or leave a building, so we can only consider the starting or end points.
Consider we already sort all building according to their starting and end point. At first, the list is empty, and when we meet the first building, we add it to the list, then move on, when we meet a new building, we check whether it will be part of the sky line (its height is larger than current sky line which is the most highest building in the list), if so, we draw the sky line before the building, otherwise, we do nothing. No matter what we do, we add this new building to the list and move on. When we leave a building, we should check whether this building is part of the sky line (it’s highest building in the list), if so, we draw the sky line out. We remove the building from the list and move on.
Below is my java code. At first, I sorted the ranges based on their starting and end point. Then I used a priority queue (heap) to speed up the max operation. For sorting is normally O(nlogn) and each heap operation is O(logn), the total time complexity is O(nlogn):
public class Solution
{
@ToString
private static class Data implements Comparable<Data>
{
final int pos;
final boolean start;
final Range range;
Data(final int pos, final boolean start, final Range range)
{
this.pos = pos;
this.start = start;
this.range = range;
}
@Override
public int compareTo(final Data o)
{
if (pos != o.pos)
{
return Integer.compare(pos, o.pos);
}
else
{
// A range with same start and end point, let the start point before end point.
if (range == o.range)
{
return (start == o.start) ? 0 : (start ? -1 : 1);
}
// Two different range, let the end point before starting point.
else
{
// Both are starting point or end point, let the range with smaller height ahead.
return (start == o.start) ? Integer.compare(range.height, o.range.height) : (start ? 1 : -1);
}
}
}
}
List<Range> skyLine(final Range[] ranges)
{
final Data[] datas = new Data[ranges.length * 2];
int i = 0;
final List<Range> result = new ArrayList<>();
for (final Range range : ranges)
{
datas[i++] = new Data(range.start, true, range);
datas[i++] = new Data(range.end, false, range);
}
Arrays.sort(datas);
final PriorityQueue<Range> heap = new PriorityQueue<>(ranges.length,
new Comparator<Range>(){
@Override
public int compare(final Range o1, final Range o2)
{
return Integer.compare(o1.height, o2.height);
}
});
int start = Integer.MIN_VALUE;
for (final Data data : datas)
{
// Start position.
if (data.start)
{
// First one.
if (heap.isEmpty())
{
start = data.pos;
}
// New starting point and has higher height.
else if (start != data.pos && heap.peek().height < data.range.height)
{
result.add(new Range(start, data.pos, heap.peek().height));
start = data.pos;
}
heap.add(data.range);
}
else
{
heap.remove(data.range);
// No building left or the one removed is highest one.
if (heap.isEmpty() || data.range.height > heap.peek().height)
{
result.add(new Range(start, data.pos, data.range.height));
start = data.pos;
}
}
}
return result;
}
}