Compute city skyline silhouette
Overview
This question evaluates understanding of computational geometry and interval-processing algorithms within the Coding & Algorithms domain, focusing on designing efficient algorithms and appropriate data-structure usage to produce correct skyline critical points.
Compute the outer silhouette of a 2D skyline. You are given n axis-aligned rectangular buildings; each building i is (Li, Ri, Hi) with 0 <= Li < Ri and Hi > 0. Return the list of critical points (x, h) where the silhouette height changes, sorted by x ascending; consecutive points must have different heights, and the final point should drop to height 0 when the skyline ends. Aim for O(n log n) time and near-linear space. Implement and explain an efficient approach (e.g., sweep line with a max-structure or divide-and-conquer). Specify and handle tie cases when multiple edges share the same x (e.g., entering edges before leaving; among entering edges process higher heights first; among leaving edges process lower heights first). Discuss correctness, complexity, and edge cases such as identical buildings, fully nested intervals, touching borders (Ri == Lj), and very large coordinates.