# Accepted Golang solution, no priority queue or heap involed

• In a linked list (it;s empty at first), each building can be considered as a range, and these ranges can overlap each other if one's height is higher than others'.
one by one put the building/range into the linked list, at last, we get whole linked list which essentially is the skyline.
the complexity should be O(n*n)

``````type Range struct {
a, b, h int
Next    *Range
}

func put(p, one *Range) *Range {
if p == nil {
return one
}
if one.a >= one.b {
//zero range
return p
}
//does not overlap
if one.a > p.b {
p.Next = put(p.Next, one)
return p
}
//overlap
if p.h >= one.h { //overlap but not overwrite
one.a = p.b
p.Next = put(p.Next, one)
} else { //one will overwrite current range
if one.b < p.b {
one.Next = &Range{one.b, p.b, p.h, p.Next}
p.b = one.a
p.Next = one
} else {
one2 := &Range{p.b, one.b, one.h, nil}
one.Next = p.Next
p.Next = one
one.b = p.b
p.b = one.a
one.Next = put(one.Next, one2)
}
}
// remove empty range as many as possible
for ; p != nil && p.a >= p.b; p = p.Next {
}
return p
}

func getSkyline(buildings [][]int) [][]int {
if len(buildings) == 0 {
return [][]int{}
}
var root *Range = nil
for _, a := range buildings {
root = put(root, &Range{a[0], a[1], a[2], nil})
}
ret := make([][]int, 0, len(buildings))
last_pos := 0
for p := root; p != nil; p = p.Next {
// remove the empty range
if p.a >= p.b {
continue
}
//fmt.Printf("%d -> %d : %d\n", p.a, p.b, p.h)
if len(ret) < 1 { // init the first one
ret = append(ret, []int{p.a, p.h})
last_pos = p.b
continue
}
// deal with the gap between two buildings
if p.a > last_pos {
ret = append(ret, []int{last_pos, 0})
}
// deal with continuous range
last_range := ret[len(ret)-1]
if p.h != last_range[1] {
ret = append(ret, []int{p.a, p.h})
}
last_pos = p.b
}
ret = append(ret, []int{last_pos, 0})
return ret
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.