The Skyline Problem

1import heapq
2from collections import defaultdict
3
4def get_skyline(buildings):
5    # Create events: (x, type, height)
6    # type: 0 = start, 1 = end
7    events = []
8    for left, right, height in buildings:
9        events.append((left, 0, height))  # building start
10        events.append((right, 1, height))  # building end
11    
12    # Sort events by x, then by type (starts before ends), then by height
13    events.sort(key=lambda x: (x[0], x[1], -x[2] if x[1] == 0 else x[2]))
14    
15    result = []
16    # Max heap for active heights (using negative values for max heap)
17    active_heights = [0]  # ground level
18    height_count = defaultdict(int)
19    height_count[0] = 1
20    
21    i = 0
22    while i < len(events):
23        curr_x = events[i][0]
24        
25        # Process all events at current x coordinate
26        while i < len(events) and events[i][0] == curr_x:
27            x, event_type, height = events[i]
28            
29            if event_type == 0:  # building start
30                active_heights.append(height)
31                height_count[height] += 1
32            else:  # building end
33                height_count[height] -= 1
34                if height_count[height] == 0:
35                    del height_count[height]
36            i += 1
37        
38        # Clean up heap - remove heights that are no longer active
39        while active_heights and active_heights[0] not in height_count:
40            heapq.heappop(active_heights)
41        
42        # Get current max height
43        if not active_heights:
44            active_heights = [0]
45            height_count[0] = 1
46        
47        # Rebuild heap to ensure max heap property
48        active_heights = sorted(height_count.keys(), reverse=True)
49        max_height = active_heights[0]
50        
51        # Add key point if height changed
52        if not result or result[-1][1] != max_height:
53            result.append([curr_x, max_height])
54    
55    return result
56
57if __name__ == "__main__":
58    # Test cases
59    
60    # Test 1: Example from problem
61    buildings1 = [[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]]
62    result1 = get_skyline(buildings1)
63    print(f"Test 1: {result1}")
64    assert result1 == [[2,10], [3,15], [7,12], [12,0], [15,10], [20,8], [24,0]], f"Expected [[2,10], [3,15], [7,12], [12,0], [15,10], [20,8], [24,0]], got {result1}"
65    
66    # Test 2: Single building
67    buildings2 = [[1,5,3]]
68    result2 = get_skyline(buildings2)
69    print(f"Test 2: {result2}")
70    assert result2 == [[1,3], [5,0]], f"Expected [[1,3], [5,0]], got {result2}"
71    
72    # Test 3: Two non-overlapping buildings
73    buildings3 = [[1,3,2], [5,8,4]]
74    result3 = get_skyline(buildings3)
75    print(f"Test 3: {result3}")
76    assert result3 == [[1,2], [3,0], [5,4], [8,0]], f"Expected [[1,2], [3,0], [5,4], [8,0]], got {result3}"
77    
78    # Test 4: Two buildings same height
79    buildings4 = [[1,4,5], [3,7,5]]
80    result4 = get_skyline(buildings4)
81    print(f"Test 4: {result4}")
82    assert result4 == [[1,5], [7,0]], f"Expected [[1,5], [7,0]], got {result4}"
83    
84    # Test 5: Complex case with 10+ buildings
85    buildings5 = [[0,2,3], [2,5,3], [1,3,2], [4,7,1], [6,10,4], [8,12,2], [11,15,5], [13,17,3], [14,18,1], [16,20,2], [19,22,4], [21,25,1]]
86    result5 = get_skyline(buildings5)
87    print(f"Test 5: {result5}")
88    
89    print("All tests passed!")

1import heapq
2from collections import defaultdict
3
4def get_skyline(buildings: list[list[int]]) -> list[list[int]]:
5    """
6    Compute skyline using sweep line algorithm with events and max heap.
7    """
8    # Create events
9    events = []
10    for left, right, height in buildings:
11        events.append((left, -height, "s"))  # start: negative height for max heap
12        events.append((right, height, "e"))   # end: positive height
13    
14    # Sort events: by x, then starts before ends, then by height appropriately
15    events.sort(key=lambda x: (x[0], x[2], x[1]))
16    
17    result = []
18    heights = [0]  # max heap (negative values), start with ground level
19    
20    for x, h, event_type in events:
21        if event_type == "s":  # building start
22            heapq.heappush(heights, h)  # h is already negative
23        else:  # building end
24            heights.remove(-h)  # remove positive height (so negate it)
25            heapq.heapify(heights)
26        
27        # Current max height is the minimum in our max heap (since values are negative)
28        max_height = -heights[0]
29        
30        # Add key point if height changes
31        if not result or result[-1][1] != max_height:
32            result.append([x, max_height])
33    
34    return result
35
36
37if __name__ == "__main__":
38    # Test 1: Example from problem
39    buildings1 = [[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]]
40    expected1 = [[2,10], [3,15], [7,12], [12,0], [15,10], [20,8], [24,0]]
41    result1 = get_skyline(buildings1)
42    print(f"Test 1: {result1 == expected1}")
43    print(f"Result: {result1}")
44    
45    # Test 2: Single building
46    buildings2 = [[0,2,3]]
47    expected2 = [[0,3], [2,0]]
48    result2 = get_skyline(buildings2)
49    print(f"Test 2: {result2 == expected2}")
50    
51    # Test 3: Two non-overlapping buildings
52    buildings3 = [[0,2,3], [4,6,2]]
53    expected3 = [[0,3], [2,0], [4,2], [6,0]]
54    result3 = get_skyline(buildings3)
55    print(f"Test 3: {result3 == expected3}")
56    
57    # Test 4: Two buildings same height
58    buildings4 = [[0,2,3], [1,3,3]]
59    expected4 = [[0,3], [3,0]]
60    result4 = get_skyline(buildings4)
61    print(f"Test 4: {result4 == expected4}")
62    
63    # Test 5: Complex case
64    buildings5 = [[0,2,3],[2,5,3],[5,7,1],[6,10,3],[8,12,2],[11,14,4],[12,15,1]]
65    result5 = get_skyline(buildings5)
66    print(f"Test 5 result: {result5}")