Digamos que se escoge la altura ~x~; entonces se deben romper los obstáculos ~i~ que salen desde abajo con altura ~\ge x~, y todos los obstáculos que salen desde arriba con altura ~\ge H - x + 1~. Si iteramos por cada ~x~ posible, debemos poder responder estas consultas (cantidad de valores ~\ge y~) de manera rápida. Una forma de hacerlo sería mantener en un arreglo las alturas de los obstáculos que salen desde arriba ordenadas, y en otro arreglo las alturas de los obstáculos que salen desde abajo ordenadas, y luego podemos hacer para cada ~x~, búsqueda binaria, obteniendo complejidad temporal ~\mathcal{O}((H + N)\cdot \log N)~ y espacial ~\mathcal{O}(N)~.

También se puede lograr complejidad ~\mathcal{O}(H + N)~, podemos llevar un arreglo de frecuencias para los obstáculos que salen desde abajo, y otro para los que salen desde arriba. Estos arreglos de frecuencia cuentan cuántas veces se repite cada altura. Luego, podemos hacer una tabla acumulativa (arreglo de sumas sufijo) sobre estos arreglos de frecuencia. Así, cada consulta saldría en tiempo ~\mathcal{O(1)}~, por tanto la complejidad temporal sería ~\mathcal{O}(H + N)~ y la complejidad espacial sería ~\mathcal{O}(H)~.

Código de ejemplo: Por añadir :)