Я пытаюсь решить знаменитую проблему горизонта (см. рисунок):

 вход

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

В случае возврата, точки, находящиеся за другими зданиями, должны исчезнуть, а координаты изменений по оси Y должны быть на возвращающемся горизонте:

(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29 0) я

Я пытаюсь сделать это, используя подход «разделяй и властвуй» к алгоритму, чтобы достичь времени выполнения O (n lg n), но яЯ застрял на части слияния.

Каждый раз, когда я думаю об этом, я запутываюсь. Например, я проверяю, какие горизонты являются первыми, например, который имеет более низкую координату X, то я добавляю это + его высота к моему новому горизонту. Но потом я сталкиваюсь с горизонтом, который скрывается за двумя другими горизонтами, как я могу это обнаружить?столкновение?

Должен ли я сначала проверить, перекрываются ли горизонты, проверив, осталось ли.x2 < right.x1? Но тогда я думаю, что я должен проверить в первую очередь? Перекрытие приоритета по оси X и все превращается в большой беспорядок куриное яйцо.

Может я'думаю слишком сложно? Что мне нужно, так это набор старших координат y на каждом пересечении, должен ли я приблизиться к нему следующим образом?