Compute city skyline silhouette

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Compute City Skyline Silhouette

You are given n axis-aligned rectangular buildings on a flat ground. Each building i is described by (Li, Ri, Hi) where 0 <= Li < Ri is its left/right x-coordinate and Hi > 0 is its height.

Compute the outer silhouette (skyline) formed by the union of all buildings. Return the list of critical points [x, h] — the points where the silhouette height changes — sorted by x ascending. The first coordinate of each key point is the x position; the second is the height there. Consecutive key points must have different heights (no redundant points), and the silhouette must terminate at a key point of height 0 where the rightmost building ends.

If there are no buildings, return an empty list.

This is the classic 'Skyline Problem'. Aim for O(n log n) time.

Tie handling (important): when multiple building edges share the same x, the algorithm must process them so the reported height is the true maximum across that x. Entering edges should be considered before leaving edges, among entering edges higher heights take effect first, and among leaving edges lower heights leave first — a sweep-line with a max-heap (and lazy deletion of ended buildings) achieves this naturally.

Example: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] → [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]].

Constraints

• 0 <= n (n is the number of buildings; n may be 0)
• Each building is [L, R, H] with 0 <= L < R and H > 0
• Coordinates and heights may be large; the algorithm only compares values, so very large coordinates are fine
• Return key points sorted by x ascending with strictly alternating heights, ending at height 0

Hints

1. Convert each building into two sweep-line events at its left and right edge, then sweep x from left to right while tracking the current maximum height among 'live' buildings.
2. Use a max-heap keyed by height. The hard part is removal: a binary heap can't pop an arbitrary element, so use lazy deletion — store each building's right edge alongside its height and discard heap-top entries whose right edge has already been passed.
3. Handle ties at a shared x carefully: process all events at the same x together, and emit a key point only when the resulting max height differs from the last emitted height. Encoding start edges as (x, -H, R) and end edges as (x, 0, 0) makes the sort order do the tie-breaking for you (starts before ends; taller starts first).

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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 ...

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.