Case File #150: Solving The Skyline Problem With CCF

Why Skyline Feels Difficult

It is tempting to begin with “Sweep Line plus Heap.” CCF begins with what must be proven: the answer, the evidence that can change it, the active scope, and what must survive movement.

Problem Statement

Given buildings [left, right, height] sorted by left boundary, construct the visible outer contour as ordered skyline key points [x, height]. Emit a point only when the visible height changes.

buildings = [[2,9,10], [3,7,15], [5,12,12]]

x:        2   3       7   9       12
building:  [----10-----]
             [----15----]
                 [-------12-------]
skyline:  [2,10] [3,15] [7,12] [12,0]

The example emits [2,10], [3,15], [7,12], and [12,0]; it never emits duplicate height 15.

At x=3, heights 10 and 15 are active, so 15 is visible. At x=7, height 15 expires and height 12 becomes visible.

Decision Space

Each emitted point extends a single contour; the final [12,0] closes it instead of returning an isolated maximum.

After x=7, active height 12 is the maximum, so the prior visible height 15 must transition to 12.

At x=5, active buildings end at 7, 9, and 12. The next unconsumed left boundary is separate Next-Scope evidence, not part of Scope.

From x=5, the next left is absent and tallest right is 7; advance directly to x=7 rather than testing x=6.

Old Scope x=3 contains active heights 15 and 10. At next x=7, height 15 expires and the retained height 12 becomes visible.

The building [5,12,12] starts at x=5, survives x=7 and x=9, then expires at x=12.

At x=3 enqueue (7,15). It becomes the heap top; at x=7 lazy removal exposes the retained (12,12) entry.

At x=12 the heap becomes empty, current height becomes zero, and [12,0] is appended to close the skyline.

First Lawful Route

The baseline event list has starts (2,10),(3,15),(5,12) and ends (7,15),(9,10),(12,12).

State-Reduction Audit

REMOVE: 2n event list. KEEP: active-building heap. After left boundary 5, tallest right 7 supplies the next x without an event object.

Direct Sweep Derivation

Candidate next x values are 3 then 5 from input, then 7 from heap top; the sequence matches the event route without event allocation.

Optimized Recorder + Complexity

The 12-Question Skyline Map

CCF-Compliant Python 3 Solution

from heapq import heappop, heappush

class Solution:
    def getSkyline(self, buildings):
        # Answer Space: ordered [x, height] key points.
        result = []
        # Problem Space: input is ordered by building left boundary.
        active = []
        index = 0
        previous = 0
        while index < len(buildings) or active:
            # Scope: next input start and active buildings.
            next_left = buildings[index][0] if index < len(buildings) else float('inf')
            next_right = active[0][1] if active else float('inf')
            # Scanner: Direct Sweep chooses the next meaningful x.
            x = min(next_left, next_right)
            while index < len(buildings) and buildings[index][0] == x:
                left, right, height = buildings[index]
                # Persistence Requirement: retain started buildings until expiry.
                heappush(active, (-height, right))
                index += 1
            while active and active[0][1] <= x:
                heappop(active)
            # Invariant: this is the maximum active height at x.
            height = -active[0][0] if active else 0
            if height != previous:
                # Finalizer: only visible height transitions enter the answer.
                result.append([x, height])
                previous = height
            # Recorder: heapq keeps active buildings ordered by negative height.
            # Efficiency Proof: next x is derived; no 2n event list is materialized.
        return result

Complexity Analysis

Time: O(n log n) time: O(n) heap insertions and removals with no event-list sorting pass.

Auxiliary space: O(n) auxiliary space for active buildings in the priority queue.

Lazy cleanup can pop several expired entries in one frame, but every entry is popped once overall, so the total cleanup is O(n log n).

Why This Is Better Than Pattern Guessing

Pattern-first says: “This is Skyline. Use Sweep Line plus Heap.” CCF asks what changes the answer, what stays true, how Scope moves, and what must survive that movement. The Scanner and Recorder then emerge as consequences of evidence.

Algorithm names are conclusions, not starting assumptions.