leetcode-go/leetcode/hard/218.the-skyline-problem.go

func getSkyline(buildings [][]int) [][]int {
	ans := [][]int{{-1, -1}} // Prevent out of index error
	var sl SortedList
	pq := NewPQ()
	length := len(buildings)
	for i, top := 0, 0; i < length || !pq.Empty(); {
		if i == length || (!pq.Empty() && pq.Peek().(Pair)._1 <= buildings[i][0]) { // Delete
			p := pq.Dequeue().(Pair)
			sl.Delete(p._2)
			if p._1 == ans[top][0] {
				ans[top][1] = sl.Max()
			} else {
				ans = append(ans, []int{p._1, sl.Max()})
				top++
			}
		} else { // Insert
			l, r, h := buildings[i][0], buildings[i][1], buildings[i][2]
			sl.Insert(h)
			pq.Enqueue(Pair{r, h})
			i++
			if l == ans[top][0] {
				ans[top][1] = sl.Max()
			} else {
				ans = append(ans, []int{l, sl.Max()})
				top++
			}
		}
		if ans[top][1] == ans[top-1][1] { // If the height is same, pop the top of ans
			ans = ans[:top]
			top--
		}
	}
	return ans[1:]
}

type SortedList struct {
	List []int
	Len  int
}

func (sl SortedList) Max() int {
	if sl.Len == 0 {
		return 0
	}
	return sl.List[sl.Len-1]
}

func (sl SortedList) Search(x int) int {
	beg, end := 0, sl.Len
	for beg < end {
		mid := beg + (end-beg)/2
		if x < sl.List[mid] {
			end = mid
		} else if sl.List[mid] < x {
			beg = mid + 1
		} else {
			return mid
		}
	}
	return beg
}

func (sl *SortedList) Insert(x int) {
	idx := sl.Search(x)
	sl.List = append(sl.List, 0)
	copy(sl.List[idx+1:], sl.List[idx:])
	sl.List[idx] = x
	sl.Len++
}

func (sl *SortedList) Delete(x int) {
	idx := sl.Search(x)
	copy(sl.List[idx:], sl.List[idx+1:])
	sl.List = sl.List[:sl.Len-1]
	sl.Len--
}

type Pair struct {
	_1 int
	_2 int
}

func (p Pair) Less(q Item) bool { return p._1 < q.(Pair)._1 }

type PQ struct {
	Queue []Item
	Len   int
}

type Item interface {
	Less(than Item) bool
}

func NewPQ() (pq PQ) {
	pq.Queue = make([]Item, 1)
	return
}

func (pq PQ) Less(i, j int) bool { return pq.Queue[i].Less(pq.Queue[j]) }
func (pq PQ) Swap(i, j int)      { pq.Queue[i], pq.Queue[j] = pq.Queue[j], pq.Queue[i] }

func (pq PQ) Empty() bool { return pq.Len == 0 }

func (pq PQ) Peek() Item { return pq.Queue[1] }

func (pq *PQ) Enqueue(item Item) {
	pq.Queue = append(pq.Queue, item)
	pq.Len++
	pq.swim(pq.Len)
}

func (pq *PQ) Dequeue() Item {
	pq.Swap(1, pq.Len)
	item := pq.Queue[pq.Len]
	pq.Queue = pq.Queue[:pq.Len]
	pq.Len--
	pq.sink(1)
	return item
}

func (pq PQ) swim(i int) {
	for 1 < i && pq.Queue[i].Less(pq.Queue[i/2]) {
		pq.Swap(i, i/2)
		i /= 2
	}
}

func (pq PQ) sink(i int) {
	for j := 2 * i; j <= pq.Len; j *= 2 {
		if j+1 <= pq.Len && pq.Queue[j+1].Less(pq.Queue[j]) {
			j++
		}
		if !pq.Queue[j].Less(pq.Queue[i]) {
			break
		}
		pq.Swap(i, j)
		i = j
	}
}