Skyline of Buildings

Question

Я пытаюсь понять проблему горизонта. Дано n прямоугольное здание, и нам нужно вычислить горизонт. У меня проблемы с пониманием результатов для этой проблемы.

Ввод: (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19 , 18,22), (23,13,29), (24,4,28)}

Выходные горизонты: (1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (25, 0)

выход пара (xaxis, height). Почему третья пара (9,0)? Если мы увидим график горизонта, значение оси x 9 имеет высоту 13, а не 0. Почему она показывает 0? Другими словами, если мы возьмем первое здание (ввод (1,11,5)), выход будет (1, 11), (5, 0). Можете ли вы объяснить, почему это (5,0) вместо (5,11)?

Answer 1

Подумайте, как интервалы на крыше будут закрыты слева и откроются справа.

Answer 2

Ваш результат не означает, что «при x высота равна y», а скорее «при x высота изменяется на y».

Answer 3

с использованием алгоритма линии развертки; вот мой питон версия Решение:

class Solution: 
    # @param {integer[][]} buildings 
    # @return {integer[][]} 
    def getSkyline(self, buildings): 
     if len(buildings)==0: return [] 
     if len(buildings)==1: return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]] 

     points=[] 
     for building in buildings: 
      points+=[[building[0],building[2]]] 
      points+=[[building[1],-building[2]]] 
     points=sorted(points, key=lambda x: x[0]) 

     moving, active, res, current=0, [0], [],-1 

     while moving<len(points): 
      i=moving 
      while i<=len(points): 
       if i<len(points) and points[i][0]==points[moving][0]: 
        if points[i][1]>0: 
         active+=[points[i][1]] 
         if points[i][1]>current: 
          current=points[i][1] 
          if len(res)>0 and res[-1][0]==points[i][0]: 
           res[-1][1]=current 
          else: 
           res+=[[points[moving][0], current]] 
        else: 
         active.remove(-points[i][1]) 
        i+=1 
       else: 
        break 

      if max(active)<current: 
       current=max(active) 
       res+=[[points[moving][0], current]] 
      moving=i 
     return res