1. Bug
If the city contains two identical buildings then skyline raises an exception:
>>> skyline(deque([(1, 2, 3), (1, 2, 3)]))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "cr66776.py", line 97, in skyline
delete(heapq.heappop(buildings_by_R)[1])
File "cr66776.py", line 87, in delete
buildings_by_H[b[1]].remove(b)
KeyError: 2
This is because the code represents buildings by tuples of numbers, and that means that two identical buildings get stored just once in a set, so when you come to remove the second building, it's not there. To fix this, buildings need to be represented such that each building is unique. One way to do this would be to use a Building class, as objects are always unique unless they implement an __eq__ method.
2. Review
It's not clear to the reader how the data is represented. The variable b represents a building, but what are b[0], b[1] and b[2]? These are the building's left x-coordinate, height, and right x-coordinate respectively, so it would make the code a lot easier to read if these were b.left, b.height, and b.right. It's easy to do this using a class, or collections.namedtuple.
It's not clear exactly what the helper functions add_point, insert, delete do. In particular, add_point doesn't always add a point to the skyline list: sometimes it updates the last point in the list. The insert function adds a building to the buildings_by_R and buildings_by_H collections, but also calls add_point. These functions could do with comments explaining what exactly it is that they do.
Some of the operations could do with a comment to explain their purpose. For example here:
h = buildings_by_H.iloc[-1] if buildings_by_H else 0
It would be worth noting that this finds the height of the highest building currently standing.
The insert and delete helper functions are only called once, so there's no particular advantage to making them into functions. The code might be clearer if these functions were inlined at the point of use.
The insert function contains the following lines of code that manipulate the vaguely named sets parameter:
def insert(b, sets=[set()]):
s = buildings_by_H.setdefault(b[1], sets[0])
s.add(b)
if s == sets[0]:
sets[0] = set()
It looks as if there was a concern that if the code were written in the obvious way:
def insert(b):
buildings_by_H.setdefault(b[1], set()).add(b)
then a set() object would be created and immediately discarded each time a building was inserted at a position for which buildings_by_H already had an entry. This is a valid concern, but the following would seem to be a clearer way to handle it:
def insert(b):
try:
s = buildings_by_H[b[1]]
except KeyError:
buildings_by_H[b[1]] = s = set()
s.add(b)
It's worth making a little effort to avoid using libraries that are not built into Python. Having to install sortedcontainers is a small but genuine barrier to running code (and might partly account for the time this question has languished without being reviewed). In this case, SortedDict is used to maintain the collection of currently standing buildings, such that (i) the height of the highest building can be found via buildings_by_H.iloc[-1]; and (ii) the set of buildings at a given height can by located via buildings_by_H[b[1]] and so a building can be removed.
However, we can implement (i) by storing the buildings in a heap, because as it says in the heapq documentation:
The interesting property of a heap is that its smallest element is always the root, heap[0].
Python heaps are min-heaps but we want the highest building, so we have to reverse the comparison order on buildings. If buildings are represented by objects, as recommended in §1 above, then this can be done by implementing a __lt__ method on the Building class.
How do we implement (ii)? You can't easily delete elements from a heap. The insight here is that we don't have to delete the building from the heap, we can leave it in the heap but mark it as finished (if buildings are represented by objects, as recommended in §1, above then this can be done by setting an attribute). We only care about the highest standing building, which is at the root of the heap, so we can just check that one to see if it is finished and pop it if so.
There's a lot of complexity in the add_point function. This complexity is due to the fact that when add_point(x) is called, we don't know whether or not we've processed all the buildings that start or end at x, so when we construct a point (x, h) we don't know whether we're done with it, or whether we might have to revise it later.
It would simplify this code considerably if we could be sure that all the buildings that start or end at x have been processed. Then we would know that the point would not need to be revised, and we could just yield it.
3. Revised code
from collections import defaultdict, namedtuple
from heapq import heappop, heappush
class Building:
def __init__(self, height):
self.height = height
self.finished = False
def __lt__(self, other):
# Reverse order by height, so that when we store buildings in
# a heap, the first building is the highest.
return other.height < self.height
# An event represents the buildings that start and end at a particular
# x-coordinate.
Event = namedtuple('Event', 'start end')
def skyline(buildings):
"""Given an iterable of buildings represented as triples (left, height,
right), generate the co-ordinates of the skyline.
>>> list(skyline([(1,9,3), (1,11,5), (2,6,7), (3,13,9), (12,7,16),
... (14,3,25), (19,18,22), (23,13,29), (24,4,28)]))
... # doctest: +NORMALIZE_WHITESPACE
[(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3),
(23, 13), (29, 0)]
>>> list(skyline([(1, 3, 2), (1, 3, 2)]))
[(1, 3), (2, 0)]
"""
# Map from x-coordinate to event.
events = defaultdict(lambda:Event(start=[], end=[]))
for left, height, right in buildings:
b = Building(height)
events[left].start.append(b)
events[right].end.append(b)
standing = [] # Heap of buildings currently standing.
last_h = 0 # Last emitted skyline height.
# Process events in order by x-coordinate.
for x, event in sorted(events.items()):
# Update buildings currently standing.
for b in event.start:
heappush(standing, b)
for b in event.end:
b.finished = True
# Pop any finished buildings from the top of the heap.
while standing and standing[0].finished:
heappop(standing)
# Top of heap (if any) is the highest standing building, so
# its height is the current height of the skyline.
h = standing[0].height if standing else 0
# Yield co-ordinates if the skyline height has changed.
if h != last_h:
yield x, h
last_h = h
4. Performance comparison
Test case (this is an order of magnitude bigger than the largest case specified in the problem description):
>>> from timeit import timeit
>>> import random
>>> R = lambda n:random.randrange(n) + 1
>>> buildings = sorted((x, R(10000), x + R(1000)) for x in (R(10000) for _ in range(50000)))
Original code:
>>> queue = deque(buildings)
>>> timeit(lambda:skyline(queue), number=1)
1.46421534800902
Revised code:
>>> timeit(lambda:list(skyline(buildings)), number=1)
0.9026356039103121
The revised code is about 40% faster than the original.
