区間スケジューリング問題とGo言語におけるライブラリを使った優先度付きキューの実装
はじめに
この記事では区間スケジューリング問題を勉強した整理を兼ねてGo言語で優先度付きキューを実装するときに使ったcontainer/heapライブラリの使い方について私的メモとしてまとめます.
区間スケジューリング問題
区間スケジューリング問題とは,複数のタスクが与えられたときに各タスクの区間(開始〜終了までの期間)が重複しないという条件下でタスクをこなせる最大の数を求める問題.例を下図に示します.図では,5つのタスクとそのスケジュールが存在します.この例では,
貪欲法による解法
- 最小の
を持つタスクR_i を選択しタスク集合から排除する.T_j -
となるタスクを新たな候補タスク集合とする.R_j \leq L_{j'} - 候補タスク集合が空集合でなければ1に戻る
つまり,終了
類似問題(競技プログラミングの鉄則 問題B39)
類似問題として,時点
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
パッケージを利用することで任意の構造体に対して簡単に優先度付きキューが実装できるので便利です.
Discussion