skyline.py

pq.py

class PriorityQueue:

    @dataclass(order=True)
    class _PrioritizedItem:
        sort_order: int
        priority: int
        item: Any = field(compare=False)

    def __init__(self):
        self.pq = []
        self.items = {}

    def add(self, item, priority):
        if priority in self.items:
            raise ValueError("already exists")        
        prioritized_item = PriorityQueue._PrioritizedItem(-priority, priority, item)
        heapq.heappush(self.pq, prioritized_item)
        self.items[priority] = prioritized_item

    def top(self):
        while self.pq:
            prioritized_item = self.pq[0]
            if prioritized_item.priority in self.items:
                return prioritized_item.item
            else:
                heapq.heappop(self.pq)
        return None

    def pop(self):
        item = self.top()
        if item is not None:
            heapq.heappop(self.pq)
            self.delete(item.priority)
        return item

    def delete(self, priority):
        if priority not in self.items:
            raise ValueError("not found")
        return self.items.pop(priority).item

skyline.py

import heapq
import itertools
from dataclasses import dataclass, field
from typing import Any

class PriorityQueue:

    @dataclass(order=True)
    class _PrioritizedItem:
        priority: int
        count: int
        item: Any = field(compare=False)

    def __init__(self):
        self.pq = [] # list of entries arranged in a heap
        self.counter = itertools.count() # count the items added so far

    def add(self, item, priority):
        count = next(self.counter)
        prioritized_item = self._PrioritizedItem(-priority, count, item)
        heapq.heappush(self.pq, prioritized_item)

    def top(self):
        while self.pq and self.pq[0].item.deleted:
            heapq.heappop(self.pq)
        return self.pq[0].item if self.pq else None

    def pop(self):
        item = self.top()
        if item is not None:
            heapq.heappop(self.pq)
        return item

class Boundary:
    def __init__(self, x, y, is_start):
        self.x = x
        self.y = y
        self.is_start = is_start
        self.other = None
        self.deleted = False

    def __lt__(self, other):
        if self.x != other.x:
            return self.x < other.x
        elif self.is_start != other.is_start:
            return self.is_start
        elif self.is_start:
            return self.y > other.y
        else:
            return self.y < other.y

    def __str__(self):
        return f"({self.x}, {self.y}, {self.is_start})"
        
    def __eq__(self, other):
        return (isinstance(other, type(self))) and all((
            self.x == other.x, 
            self.y == other.y, 
            self.is_start == other.is_start,
        ))

    def __hash__(self):
        return hash((self.x, self.y, self.is_start))
        
def get_ordered_boundaries(buildings) -> list[Boundary]:
    boundaries = []
    for building in buildings:
        start, end, y = building
        start_boundary = Boundary(start, y, True)
        end_boundary = Boundary(end, y, False)
        start_boundary.other = end_boundary
        end_boundary.other = start_boundary
        boundaries.append(start_boundary)
        boundaries.append(end_boundary)
    return sorted(boundaries)

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        pq = PriorityQueue()
        result = []
        current_x = None
        current_y = -1
        for boundary in get_ordered_boundaries(buildings):
            # print("111", boundary)
            if boundary.is_start:
                pq.add(boundary, boundary.y)
                if boundary.y > current_y:
                    current_x = boundary.x
                    current_y = boundary.y
                    result.append([current_x, current_y])                    
            else:
                boundary.other.deleted = True
                # print(current_y)
                if boundary.y == current_y:
                    # print("222", boundary)
                    current_x = boundary.x
                    current_boundary = pq.top()
                    if current_boundary is None:                        
                        current_y = -1
                        result.append([current_x, 0])
                    elif current_y != current_boundary.y:
                        current_y = current_boundary.y
                        result.append([current_x, current_y])
        return result