We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

The Skyline Problem

Difficulty: Hard

Problem Description

Given the locations and heights of all the buildings in a city, return the skyline formed by these buildings collectively. The skyline should be represented as a list of key points sorted by their x-coordinate. Each key point is the left endpoint of some horizontal segment in the skyline, except the last point which always has a y-coordinate of 0 to mark the skyline's termination.

Key Insights

  • The skyline can be determined using a line sweep algorithm combined with a max-heap (priority queue) to keep track of active building heights.
  • By processing "events" (start and end of buildings), we can determine when to add or remove heights from the skyline.
  • We must ensure that consecutive points with the same height are merged to avoid horizontal lines in the output.

Space and Time Complexity

Time Complexity: O(N log N) - where N is the number of buildings, due to sorting and heap operations. Space Complexity: O(N) - for storing the heights in the heap and the output list.

Solution

To solve this problem, we will use the line sweep algorithm. We will create a list of events for each building: one for the start (left edge) and one for the end (right edge). We will sort these events primarily by the x-coordinate, and in case of ties, we will prioritize the start of a building over its end. We will utilize a max-heap to keep track of the current active building heights. As we process each event, we will compare the current maximum height with the height from the heap and record key points whenever there is a change in height.

Code Solutions

from heapq import heappop, heappush

def getSkyline(buildings):
    events = []
    for left, right, height in buildings:
        events.append((left, -height))  # Start of building
        events.append((right, height))   # End of building
    
    # Sort events by x coordinate, then by height
    events.sort()

    result = []
    max_heap = [(0, float('inf'))]  # (height, right_end)
    curr_height = 0

    for x, h in events:
        if h < 0:  # Start of a building
            heappush(max_heap, (h, x))  # Push negative height to max-heap
        else:  # End of a building
            max_heap = [(height, right) for height, right in max_heap if right > x]  # Remove ended buildings
            heapify(max_heap)

        # Get the current max height
        if max_heap:
            new_height = -max_heap[0][0]
        else:
            new_height = 0

        # If there is a change in height, add to result
        if new_height != curr_height:
            result.append([x, new_height])
            curr_height = new_height

    return result
← Back to All Questions