😊

区間スケジューリング問題とGo言語におけるライブラリを使った優先度付きキューの実装

2022/10/31に公開

Golang

tech

はじめに

この記事では区間スケジューリング問題を勉強した整理を兼ねてGo言語で優先度付きキューを実装するときに使ったcontainer/heapライブラリの使い方について私的メモとしてまとめます．

区間スケジューリング問題

区間スケジューリング問題とは，複数のタスクが与えられたときに各タスクの区間（開始〜終了までの期間）が重複しないという条件下でタスクをこなせる最大の数を求める問題．例を下図に示します．図では，5つのタスクとそのスケジュールが存在します．この例では，

貪欲法による解法

$i$ 番目のタスク $T_i$ の区間の開始を $L_i$ ，終了を $R_i$ とします．このとき，タスクの集合に対して以下のようにタスクを選択することで最適な区間スケジューリングができます．

最小の $R_i$ を持つタスク $T_j$ を選択しタスク集合から排除する．
$R_j \leq L_{j'}$ となるタスクを新たな候補タスク集合とする．
候補タスク集合が空集合でなければ1に戻る

つまり，終了 $R_i$ でソートしたタスク配列に対して重複しない条件を満たすタスクを順番に取っていけば最適な区間スケジューリングが達成できます．

類似問題（競技プログラミングの鉄則問題B39）

類似問題として，時点 $t$ ごとに報酬 $R$ のタスク $T$ が発生し， $t$ 時点のタスク集合から逐次的に選択していき $D$ 時点目で得られる合計報酬を最大化する問題があります（詳細は下のリンクより）．この問題では，全てのタスクをあらかじめソートしておくことはできないので，優先度付きキューをつかって $t$ 時点の最大報酬額をもつタスク $T'$ を逐次選択することになります．

container/heapパッケージによる優先度付きキューの実装

上記の問題を解くためにGo言語で優先度付きキューを実装した際に便利だったcontainer/heapパッケージの使い方をメモしておきます．基本的には公式ページの例に書いてあるとおりです．

container/heapパッケージではinterface型を用意しており，必要なインターフェースを実装するだけで優先度付きキューを実装できます．具体的には，例えばint型の要素をもつヒープキューを実装したい場合，以下の
5つの関数を実装しておけばcontainer/heapが受け入れられる構造体となります．

type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
// 値を降順にしたい場合は不等号を逆にする
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

利用する際は，先程の構造体をheapパッケージのInit関数で取り込むことで優先度付きキューが実装され，あとはよしなにPushやPopの操作を行うことができます．

func main() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h)
	heap.Push(h, 3)
	fmt.Printf("minimum: %d\n", (*h)[0])
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}
}

おわりに

C++にはpriority_queueがあるけどGoで簡単に使えるものはないかなと思っていましたが，container/heapパッケージを利用することで任意の構造体に対して簡単に優先度付きキューが実装できるので便利です．