forked from adnanaziz/EPIJudge
-
Notifications
You must be signed in to change notification settings - Fork 0
/
drawing_skyline.py
43 lines (30 loc) · 1.34 KB
/
drawing_skyline.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import collections
import functools
from test_framework import generic_test
from test_framework.test_utils import enable_executor_hook
Rectangle = collections.namedtuple('Rectangle', ('left', 'right', 'height'))
def compute_skyline(buildings):
min_left = min(buildings, key=lambda b: b.left).left
max_right = max(buildings, key=lambda b: b.right).right
heights = [0] * (max_right - min_left + 1)
for building in buildings:
for i in range(building.left, building.right + 1):
heights[i - min_left] = max(heights[i - min_left], building.height)
result = []
left = 0
for i in range(1, len(heights)):
if heights[i] != heights[i - 1]:
result.append(
Rectangle(left + min_left, i - 1 + min_left, heights[i - 1]))
left = i
return result + [Rectangle(left + min_left, max_right, heights[-1])]
@enable_executor_hook
def compute_skyline_wrapper(executor, buildings):
buildings = [Rectangle(*x) for x in buildings]
result = executor.run(functools.partial(compute_skyline, buildings))
return [(x.left, x.right, x.height) for x in result]
if __name__ == '__main__':
exit(
generic_test.generic_test_main("drawing_skyline.py",
'drawing_skyline.tsv',
compute_skyline_wrapper))