Estou tentando resolver o famoso problema do horizonte (veja gif):

 Entrada

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

Deve retornar, os pontos que estão por trás de outros edifícios devem desaparecer e as coordenadas de mudanças no eixo Y devem estar no horizonte de retorno:

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

Eu estou tentando fazer isso usando uma abordagem de divisão e conquista para o algoritmo, a fim de alcançar um tempo de execução de O (n lg n), mas estou preso na parte de mesclagem.

Toda vez que penso nisso fico confuso. Por exemplo, eu verifico qual das skylines é a primeira, por ex. que tem a coordenada x menor, então eu adiciono isso + sua altura ao meu novo horizonte. Mas então eu me deparo com uma linha do horizonte por trás de outras duas skylines, como posso detectar essa 'colisão'?

Eu primeiro verifico se as skylines têm alguma sobreposição verificando se left.x2 <right.x1? Mas então eu acho que devo verificar primeiro? Sobreposição de precedência no eixo xe tudo se transforma em uma grande bagunça de ovo de galinha.

Talvez eu esteja pensando muito complicado? O que eu preciso é o conjunto de coordenadas y mais altas, em cada cruzamento, devo abordá-lo assim?