# [Classic, Bisect-Lower-Bound, Time-Series]
# https://leetcode.com/problems/the-skyline-problem/
# 218. The Skyline Problem

# History:
# Netflix
# 1.
# May 6, 2020

# A city's skyline is the outer contour of the silhouette formed by all the buildings in that
# city when viewed from a distance. Now suppose you are given the locations and height of all the
# buildings as shown on a cityscape photo (Figure A), write a program to output the skyline
# formed by these buildings collectively (Figure B).
#
# Buildings Skyline Contour
# The geometric information of each building is represented by a triplet of integers [Li, Ri,
# Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building,
# respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤
# INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an
# absolutely flat surface at height 0.
#
# For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10],
# [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
#
# The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2,
# y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a
# horizontal line segment. Note that the last key point, where the rightmost building ends,
# is merely used to mark the termination of the skyline, and always has zero height. Also,
# the ground in between any two adjacent buildings should be considered part of the skyline contour.
#
# For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12],
# [12 0], [15 10], [20 8], [24, 0] ].
#
# Notes:
#
# The number of buildings in any input list is guaranteed to be in the range [0, 10000].
# The input list is already sorted in ascending order by the left x position Li.
# The output list must be sorted by the x position.
# There must be no consecutive horizo


class HeapWithRandomDelete(object):
    def __init__(self):
        self.lst = []

    def _bisect(self, height):
        l, r = 0, len(self.lst)

        while l < r:
            m = (r - l) / 2 + l

            if self.lst[m] >= height:
                r = m
            else:
                l = m + 1

        return l

    def add(self, height):
        pos = self._bisect(height)

        self.lst.insert(pos, height)

    def remove(self, height):
        pos = self._bisect(height)

        if pos < len(self.lst) and self.lst[pos] == height:
            self.lst.pop(pos)

    def get_heighest(self):
        return self.lst[-1] if self.lst else 0


class Solution(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        heap = HeapWithRandomDelete()

        events = []
        for s, e, height in buildings:
            events.append((s, -height))
            events.append((e, height))

        events.sort()

        ret = []
        pre = None
        for t, height in events:
            if height > 0:
                heap.remove(height)
            else:
                heap.add(-height)

            highest = heap.get_heighest()

            if highest != pre:
                pre = highest
                ret.append([t, highest])

        return ret
