The Skyline Problem

class MaxHeap:
    def __init__(self, buildings):
        self.buildings = buildings
        self.size = 0
        self.heap = [None] * (2 * len(buildings) + 1)
        self.lineMap = dict()
    def maxLine(self):
        return self.heap[1]
    def insert(self, lineId):
        self.size += 1
        self.heap[self.size] = lineId
        self.lineMap[lineId] = self.size
        self.siftUp(self.size)
    def delete(self, lineId):
        heapIdx = self.lineMap[lineId]
        self.heap[heapIdx] = self.heap[self.size]
        self.lineMap[self.heap[self.size]] = heapIdx
        self.heap[self.size] = None
        del self.lineMap[lineId]
        self.size -= 1
        self.siftDown(heapIdx)
    def siftUp(self, idx):
        while idx > 1 and self.cmp(idx / 2, idx) < 0:
            self.swap(idx / 2, idx)
            idx /= 2
    def siftDown(self, idx):
        while idx * 2 <= self.size:
            nidx = idx * 2
            if idx * 2 + 1 <= self.size and self.cmp(idx * 2 + 1, idx * 2) > 0:
                nidx = idx * 2 + 1
            if self.cmp(nidx, idx) > 0:
                self.swap(nidx, idx)
                idx = nidx
            else:
                break
    def swap(self, a, b):
        la, lb = self.heap[a], self.heap[b]
        self.lineMap[la], self.lineMap[lb] = self.lineMap[lb], self.lineMap[la]
        self.heap[a], self.heap[b] = lb, la
    def cmp(self, a, b):
        return self.buildings[self.heap[a]][2] - self.buildings[self.heap[b]][2]

class Solution:
    def getSkyline(self, buildings):
        size = len(buildings)
        points = sorted([(buildings[x][0], x, 's') for x in range(size)] + 
                        [(buildings[x][1], x, 'e') for x in range(size)])
        maxHeap = MaxHeap(buildings)
        ans = []
        for p in points:
            if p[2] == 's':
                maxHeap.insert(p[1])
            else:
                maxHeap.delete(p[1])
            maxLine = maxHeap.maxLine()
            height = buildings[maxLine][2] if maxLine is not None else 0
            if len(ans) == 0 or ans[-1][0] != p[0]:
                ans.append([p[0], height])
            elif p[2] == 's':
                ans[-1][1] = max(ans[-1][1], height)
            else:
                ans[-1][1] = min(ans[-1][1], height)
            if len(ans) > 1 and ans[-1][1] == ans[-2][1]:
                ans.pop()
        return ans

public class Solution {
    //大顶推比较器
    public class MaxCom implements Comparator<Integer> {
        public int compare(Integer a, Integer b){
            return b - a ; // 大的在堆的顶端
        }
    } 
    //数组比较器
    public class ArrayCom implements Comparator<int[]> {
        public int compare(int[] a, int[] b) {
            if(a[0] != b[0]) return a[0] - b[0];  //先按左边界进行排序
            return b[1] - a[1];  // 相等 则高的在前面
        }
    }
    public List<int[]> getSkyline(int[][] buildings) {  
        List<int[]> res = new ArrayList<int[]>();  
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new MaxCom());
        
        List<int[]> ver = new ArrayList<int[]>();  // 记录每一个竖线
        for(int i = 0 ; i < buildings.length ; i++){
            int[] temp = buildings[i]; 
            ver.add(new int[]{temp[0], temp[2]});  // 左边界竖线
            ver.add(new int[]{temp[1], -temp[2]});  // 右边界竖线 为了区分 存入负值
        }
        Collections.sort(ver, new ArrayCom());
        
        int cur = 0, pre = 0;
        for(int i = 0 ; i < ver.size() ; i++){
            int[] temp = ver.get(i);
            if(temp[1] > 0) {  // 左边界
                maxHeap.offer(temp[1]);  //高度入队
                cur = maxHeap.peek(); // 当前最高的
            }else { // 右边界
                maxHeap.remove(-temp[1]);  // 将对应的高度从堆中删除 这里就是右边存负值的方便之处
                cur = (maxHeap.peek() == null ? 0 : maxHeap.peek()); // 如果右边界是最后一个则高度为0，否则更新当前最高
            }
            if(cur != pre) {  // 与上一个最高的不相等
                res.add(new int[]{temp[0], cur});
                pre = cur;  // 保存当前高度为下一次的前面高度
            }
        }
        return res;       
    }
}

class Solution {
private:
    enum NODE_TYPE {LEFT, RIGHT};
    struct node {
        int x, y;
        NODE_TYPE type;
        node(int _x, int _y, NODE_TYPE _type) : x(_x), y(_y), type(_type) {}
    };
    
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<node> height;
        for (auto &b : buildings) {
            height.push_back(node(b[0], b[2], LEFT));
            height.push_back(node(b[1], b[2], RIGHT));
        }
        sort(height.begin(), height.end(), [](const node &a, const node &b) {
            if (a.x != b.x) return a.x < b.x;
            else if (a.type == LEFT && b.type == LEFT) return a.y > b.y;
            else if (a.type == RIGHT && b.type == RIGHT) return a.y < b.y;
            else return a.type == LEFT;
        });
        
        priority_queue<int> heap;
        unordered_map<int, int> mp;
        heap.push(0);
        vector<pair<int, int>> res;
        int pre = 0, cur = 0;
        for (auto &h : height) {
            if (h.type == LEFT) {
                heap.push(h.y);
            } else {
                ++mp[h.y];
                while (!heap.empty() && mp[heap.top()] > 0) {
                    --mp[heap.top()];
                    heap.pop();
                }
            }   
            cur = heap.top();
            if (cur != pre) {
                res.push_back({h.x, cur});
                pre = cur;
            }
        }
        return res;
    }
};