Approach: Sweep Line Max-Heap (lazy deletion)Turn each building into two events — a start at“l” (encoded as“-h”) and an end at“r” (encoded as“h”). Sweep left to right with a max-heap of active heights. The skyline only changes when the heap’s max changes.Two details make it correct:Encoding by sign lets one comparator handle tie-breaking: at the same“x”, sorting by height ascending puts tall starts first, then short starts, then ends — so a taller building starting where a shorter one ends doesn’t create a phantom dip.Lazy deletion: on an end event we don’t scan the heap (that’d be“O(n)”); we bump a counter in a map and only purge the top while it’s marked dead, right before reading the max.class Solution {public ListList getSkyline(int[][] buildings) {// event {x, signedHeight}; negative start, positive endListint[] events new ArrayList();for (int[] b : buildings) {events.add(new int[]{b[0], -b[2]});events.add(new int[]{b[1], b[2]});}events.sort((a, b) - a[0] ! b[0]? Integer.compare(a[0], b[0]): Integer.compare(a[1], b[1]));// max-heap of active heights, 0 ground sentinel PriorityQueueInteger heap new PriorityQueue(Collections.reverseOrder()); MapInteger, Integer dead new HashMap(); // height - pending removals heap.offer(0); ListListInteger res new ArrayList(); int prev 0; for (int i 0; i events.size(); ) { int x events.get(i)[0]; // process ALL events at this x before sampling the skyline while (i events.size() events.get(i)[0] x) { int h events.get(i)[1]; if (h 0) { heap.offer(-h); // start } else { dead.merge(h, 1, Integer::sum); // end (lazy) } i; } // purge dead entries sitting on top while (dead.getOrDefault(heap.peek(), 0) 0) { int top heap.poll(); int cnt dead.get(top); if (cnt 1) dead.remove(top); else dead.put(top, cnt - 1); } int cur heap.peek(); if (cur ! prev) { res.add(Arrays.asList(x, cur)); prev cur; } } return res; }}ComplexityTime“O(n log n)” — sorting the“2n” events dominates; each heap push/pop is“O(log n)”, and lazy deletion amortizes to one pop per pushSpace“O(n)” — event list, heap, and dead mapWhy the details matterGrouping by“x” is required. If you sample the heap after each individual event, two buildings sharing an edge (one ending at“x”, one starting at“x”) emit a spurious intermediate point. Grouping collapses them into one decision.The“0” sentinel removes the“isEmpty()” branch when the skyline drops back to ground level.Sign encoding beats a 3-field event object — fewer allocations, and the comparator stays a one-liner. Just remember“h 0” is an end, which reads backwards at first glance.A divide-and-conquer alternative also runs in“O(n log n)” by merging skylines pairwise, but it’s noticeably more code for the same asymptotic cost — the heap version is the one worth writing under time pressure.