5.6 A Divide-and-Conquer Algorithm: The Skyline Problem - Introduction to Algorithms by Udi Manber

skyline.go

package main

import (
	"fmt"
)

type Building struct {
	left   int
	height int
	right  int
}

func (b Building) ToSkyline() Skyline {
	return Skyline{{b.left, b.height}, {b.right, 0}}
}

type Line struct {
	x int
	h int
}

type Skyline []Line

// 候補の位置で高さ変更するかどうか
// candidate: 追加するか判定する候補の水平線
// other: candidateのx座標とかぶる相手の水平線 candidate.x > other.x
// currentH: 現在の水平線の高さ
// 高さ変更する場合水平線の開始座標を返す
// 変更しない場合はnilを返す
func check(canditate Line, other Line, currentH int) *Line {
	if canditate.h > other.h {
		// 候補の方が高ければ追加
		return &canditate
	} else if canditate.h == other.h && canditate.h != currentH {
		// 高さが同じ場合、現在の輪郭線の高さと異なる場合は追加
		return &canditate
	} else if canditate.h < other.h && other.h != currentH {
		// 低い場合は相手の輪郭線の高さまで引き上げる
		return &Line{canditate.x, other.h}
	}

	return nil
}

func merge(a Skyline, b Skyline) Skyline {
	result := Skyline{}
	h := 0
	i, j := 0, 0

	// 重ならない左側の水平線を追加
	for i < len(a) && a[i].x < b[0].x {
		h = a[i].h
		result = append(result, a[i])
		i++
	}

	for j < len(b) && b[j].x < a[0].x {
		h = b[j].h
		result = append(result, b[j])
		j++
	}

	// 重なり合う部分の判定
	for i < len(a) && j < len(b) {
		if a[i].x < b[j].x {
			if res := check(a[i], b[j-1], h); res != nil {
				result = append(result, *res)
				h = res.h
			}
			i++
		} else {
			if res := check(b[j], a[i-1], h); res != nil {
				result = append(result, *res)
				h = res.h
			}
			j++
		}
	}

	// 重ならない右側の水平線を追加 （残り）
	for j < len(b) {
		result = append(result, b[j])
		j++
	}

	for i < len(a) {
		result = append(result, a[i])
		i++
	}

	return result
}

func resolve(bs []Building) Skyline {
	length := len(bs)
	if length == 1 {
		return bs[0].ToSkyline()
	}

	return merge(resolve(bs[:length/2]), resolve(bs[length/2:]))
}

func test_merge(s1 Skyline, s2 Skyline) {
	fmt.Printf("%v\n", merge(s1, s2))
	fmt.Printf("%v\n", merge(s2, s1))
}

func test_resolve(bs []Building) {
	fmt.Printf("%v\n", resolve(bs))
}

func main() {
	test_merge(Skyline{{1, 2}, {2, 0}}, Skyline{{3, 2}, {4, 0}})
	test_merge(Skyline{{1, 2}, {3, 0}}, Skyline{{2, 3}, {4, 0}})
	test_merge(Skyline{{1, 3}, {3, 0}}, Skyline{{2, 2}, {4, 0}})
	test_merge(Skyline{{1, 3}, {5, 0}}, Skyline{{2, 5}, {3, 3}, {4, 2}, {7, 0}})
	test_merge(Skyline{{2, 4}, {3, 3}, {5, 5}, {7, 2}, {9, 0}}, Skyline{{4, 2}, {5, 1}, {6, 6}, {8, 1}, {11, 0}})
	test_merge(Skyline{{1, 2}, {4, 0}, {8, 2}, {10, 0}}, Skyline{{5, 2}, {7, 0}})

	test_resolve([]Building{{1, 2, 4}, {5, 2, 7}, {8, 2, 10}})
	test_resolve([]Building{{1, 11, 5}, {2, 6, 7}, {3, 13, 9}, {12, 7, 16}, {14, 3, 25}, {19, 18, 22}, {23, 13, 29}, {24, 4, 28}})
}