Skip to content
Newer
Older
100644 86 lines (76 sloc) 2.63 KB
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
1 /**
2 * The Skyline Problem
3 * http://online-judge.uva.es/p/v1/105.html
4 *
5 * Sweep Line Algorithm
6 * http://www.algorithmist.com/index.php/UVa_105
17825f5 Removed complexity from skyline algorithm
Andrey Paramonov authored
7 *
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
8 * To implement the algorithm we need two data structures:
9 * - min-heap to store insert-remove events, and
17825f5 Removed complexity from skyline algorithm
Andrey Paramonov authored
10 * - max-heap to store building heights.
11 *
12 * With these data structures the running time of the algorithm is O(n log n).
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
13 */
17825f5 Removed complexity from skyline algorithm
Andrey Paramonov authored
14 import static Operation.*
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
15
16 enum Operation {
17 INSERT, REMOVE
18 }
19
20 class Event {
21 Integer coordinate
22 Integer height
23 Operation operation
24 }
25
17825f5 Removed complexity from skyline algorithm
Andrey Paramonov authored
26 /*
27 * The core of the algorithm is to sort all events properly.
28 * With sorted events, the rest of the algorithm is pretty simple.
29 */
30 class EventComporator implements Comparator<Event> {
31 int compare(Event p, Event q) {
32 if (p.coordinate != q.coordinate) return p.coordinate.compareTo(q.coordinate)
33 if (p.operation == INSERT && q.operation == INSERT) return q.height.compareTo(p.height)
34 if (p.operation == REMOVE && q.operation == REMOVE) return p.height.compareTo(q.height)
35 p.operation == INSERT ? -1 : 1
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
36 }
37 }
38
39 /*
17825f5 Removed complexity from skyline algorithm
Andrey Paramonov authored
40 * Main algorithm.
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
41 */
42 def skyline(buildings) {
14419e5 Minor cleanup and refactoring
Andrey Paramonov authored
43 processEvents(buildEventHeap(buildings))
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
44 }
45
17825f5 Removed complexity from skyline algorithm
Andrey Paramonov authored
46 /*
47 * Insert 2n entries into min-heap.
48 * Running time is O(n log n)
49 */
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
50 def buildEventHeap(buildings) {
17825f5 Removed complexity from skyline algorithm
Andrey Paramonov authored
51 def result = new PriorityQueue<Event>(2 * buildings.size(), new EventComporator())
52 buildings.each { // it = [left_coordinate, height, right_coordinate]
53 result << new Event(coordinate: it[0], height: it[1], operation: INSERT)
54 result << new Event(coordinate: it[2], height: it[1], operation: REMOVE)
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
55 }
56 result
57 }
58
17825f5 Removed complexity from skyline algorithm
Andrey Paramonov authored
59 /*
60 * Loop through the event heap and check if the height is being changed.
61 * If so, add event's coordinate and height to the result list.
62 * Running time is O(n log n).
63 */
14419e5 Minor cleanup and refactoring
Andrey Paramonov authored
64 def processEvents(eventHeap) {
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
65 def result = []
ce77de7 @ndpar Cosmetics
authored
66 def heights = new PriorityQueue<Integer>(eventHeap.size(), {n,m -> m.compareTo(n)} as Comparator)
17825f5 Removed complexity from skyline algorithm
Andrey Paramonov authored
67 int lastMaxHeight = 0
68 while ((event = eventHeap.poll()) != null) { // 2n * O(log n)
69 event.operation == INSERT ? heights.add(event.height) : heights.remove(event.height) // O(log n)
70 int currentMaxHeight = heights.peek() ?: 0 // O(1)
71 if (lastMaxHeight != currentMaxHeight) {
72 result << event.coordinate << currentMaxHeight
73 lastMaxHeight = currentMaxHeight
b5b16aa Solved Skyline Problem
Andrey Paramonov authored
74 }
75 }
76 result
77 }
78
79
80 assert [2,4,8,0] == skyline([[2,4,5],[4,4,8]])
81 assert [2,4,8,0] == skyline([[2,4,5],[5,4,8]])
82 assert [2,4,6,0] == skyline([[2,4,6],[2,2,6]])
83
84 assert [1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0] ==
85 skyline([[1,11,5],[2,6,7],[3,13,9],[12,7,16],[14,3,25],[19,18,22],[23,13,29],[24,4,28]])
Something went wrong with that request. Please try again.