HàPhan 河

Detail of this problem can be found here.

https://leetcode.com/problems/the-skyline-problem/

We will be given a list of buildings.
A building can be represented by a triplet of integers `[Li, Ri, Hi]`, equivalent to 4 points in XY coordinate: `(0, Li)`, `(0, Ri)`, `(Hi, Li)`, `(Hi, Ri)`.

Then we need to return list of points `(x, y)` that could make a skyline view below:

You can watch the video below, Tushar Roy explained so clearly.

I summarize those key steps:

• Separate a building to 2 lines : `(x1, y1, start)`, `(x2, y1, end)`

• Sort all lines of all buildings by `x`, if `x` is same, we need a tiebreaker rule
Tie-breaker rule contains 3 conditions: all `start`s (higher `y` comes first), all `end`s (lower `y` comes first), one `start` + one `end` (`start` comes first). Explaination could be found in the video.

• Iterate through list of lines, then put/remove a line to Priority Queue with `y` is priority factor.

• When meet a start line, put it to `PriorityQueue`, if max of the queue is changed, mark `(x,y)` of the line as an output point.
• When meet a end line, remove the start line in `PriorityQueue`, if max of the queue is changed, mark `(x,y)` of the line as an output point.

Let start to implement:
We define a data structure for line first.

``````struct Skyline {
var point: (x: Int, height: Int)
var isStart: Bool

static func getSkylines(from building: (L: Int, R: Int, H: Int)) -> [Skyline] {
return [
Skyline(point: (x: building.L, height: building.H), isStart: true),
Skyline(point: (x: building.R, height: building.H), isStart: false)
]
}

static func getSkylines(from building: [Int]) -> [Skyline] {
return self.getSkylines(from: (L: building[0], R: building[1], H: building[2]))
}
}

extension Skyline : Comparable {
static func == (lhs: Skyline, rhs: Skyline) -> Bool {
return lhs.point.x == rhs.point.x && lhs.point.height == rhs.point.height && lhs.isStart == rhs.isStart
}

static func < (lhs: Skyline, rhs: Skyline) -> Bool {

//normal case
guard lhs.point.x == rhs.point.x else {
return lhs.point.x < rhs.point.x
}

//same type
guard lhs.isStart == rhs.isStart else {
return lhs.isStart
}

//different type
if lhs.isStart {
return lhs.point.height > rhs.point.height
} else {
return lhs.point.height < rhs.point.height
}
}
}
``````

Next priority queue and priority elements

``````struct PriorityQueue<Element: Equatable> {
var heap: Heap<Element>

var isEmpty: Bool {
return heap.isEmpty
}

init(elements: [Element], priorityFunction: @escaping (Element, Element) -> Bool) {
heap = Heap(elements: elements, priorityFunction: priorityFunction)
}

mutating func enqueue(_ item: Element) {
heap.enqueue(item)
}

mutating func dequeue() -> Element? {
return heap.dequeue()
}

mutating func peek() -> Element? {
return heap.peek()
}

mutating func remove(_ element: Element) {
return heap.remove(element)
}
}

struct Heap<Element: Equatable> {
var elements: [Element]
let priorityFunction: (Element, Element) -> Bool

init(elements: [Element], priorityFunction: @escaping (Element, Element) -> Bool) {
self.elements = elements
self.priorityFunction = priorityFunction
buildHeap()
}

var isEmpty: Bool {
return elements.count == 0
}
var count: Int {
return elements.count
}

//Helper
func isRoot(_ index: Int) -> Bool {
return index == 0
}
func getLeftChildIndex(of index: Int) -> Int {
return (2 * index) + 1
}
func getRightChildIndex(of index: Int) -> Int {
return (2 * index) + 2
}
func getParentIndex(of index: Int) -> Int {
return (index - 1) / 2
}
func getElement(at index: Int) -> Element? {
guard index < elements.count else {
return nil
}
return elements[index]
}
func isHigherPriority(at index: Int, than secondIndex: Int) -> Bool {
let el1 = getElement(at: index)
let el2 = getElement(at: secondIndex)
if el1 == nil && el2 != nil {
return false
}
if el2 == nil && el1 != nil {
return true
}
if el2 == nil && el1 == nil {
return false
}
return priorityFunction(el1!, el2!)
}

func getFamilyHighest(at index: Int) -> Int {
let children1 = getLeftChildIndex(of: index)
let children2 = getRightChildIndex(of: index)
let maxChild = isHigherPriority(at: children1, than: children2) ? children1 : children2
return isHigherPriority(at: index, than: maxChild) ? index : maxChild
}

mutating func swap(at index: Int, with secondIndex: Int) {
guard index != secondIndex else {
return
}
elements.swapAt(index, secondIndex)
}

//Heap sift function
mutating func siftUp(at index: Int) {
guard !isRoot(index) else { return }

let parent = getParentIndex(of: index)
if !isHigherPriority(at: index, than: parent) {
return
}

swap(at: index, with: parent)
siftUp(at: parent)
}
mutating func siftDown(at index: Int) {
let highestIndex = getFamilyHighest(at: index)
if index == highestIndex {
return
}
swap(at: index, with: highestIndex)
siftDown(at: highestIndex)
}
mutating func buildHeap() {
for index in (0 ..< count / 2).reversed() {
siftDown(at: index)
}
}

//Queue function
mutating func enqueue(_ element: Element) {
elements.append(element)
siftUp(at: count - 1)
}

mutating func dequeue() -> Element? {
guard !isEmpty else { return nil }
swap(at: 0, with: count - 1)
let ele = elements.removeLast()
if !isEmpty{
siftDown(at: 0)
}
return ele
}

mutating func peek() -> Element? {
return elements.first
}

//temporary
mutating func remove(_ element: Element) {
if let index = elements.firstIndex(where: { \$0 == element}) {
elements.remove(at: index)
buildHeap()
}
}
}

struct QueueElement {
var height: Int
var point: (x: Int, y: Int)

init() {
height = 0
point = (x: 0, y: 0)
}

init(_ skyline: Skyline) {
height = skyline.point.height
point = (x: skyline.point.x, y: skyline.point.height)
}
}

extension QueueElement : Comparable {
static func == (lhs: QueueElement, rhs: QueueElement) -> Bool {
return lhs.height == rhs.height
}
static func < (lhs: QueueElement, rhs: QueueElement) -> Bool {
return lhs.height < rhs.height
}
}
``````

Because this Priority Queue doesn't support removing a specific element, I tried to add a `remove(_:)` function with `removeElement` and `buildHeap` as part.
But it takes `O(n)` time.

Below are solution function

``````func getSkyline(_ buildings: [[Int]]) -> [[Int]] {
var result: [[Int]] = []
var skylines: [Skyline] = []

for building in buildings {
skylines.append(contentsOf: Skyline.getSkylines(from: building))
}

skylines.sort()

var queue = PriorityQueue<QueueElement>(elements: [QueueElement()], priorityFunction: { \$0 > \$1})

for skyline in skylines {
let currentMax = queue.peek()!
if skyline.isStart {
queue.enqueue(QueueElement(skyline))
}else{
queue.remove(QueueElement(skyline))
}

let newMax = queue.peek()!
if currentMax != newMax {
if skyline.isStart {
result.append([skyline.point.x, skyline.point.height])
}else{
result.append([skyline.point.x, newMax.height])
}
}

}

return result
}
``````

`PriorityQueue` does not support remove element with `LogN` time. To totally resolve this problem, there must be a replacement.

I will update later.