【C#】区間スケジューリング問題における解法の説明と実装について
キーエンス プログラミング コンテスト 2020で区間スケジューリング問題がでたのですが、覚えていれば実装できる問題だったので、改めて整理してみたいと思います。
はじめに
本記事のテーマ
区間スケジューリング問題とは何か、どう実装すればよいか説明します。後半で今回のネタ元となるキーエンス プログラミングコンテストの問題を例題として説明します。
本題
区間スケジューリング問題とは
区間スケジューリング問題とは 貪欲法に分類される解法の一つです。貪欲法の定義は、蟻本(プログラミングコンテストチャレンジブック)にのっている定義を引用させていただくと
貪欲法とは”1つのルールに従って、貪欲的に「その場での最善」を選択することを繰り返す”というアルゴリズム設計技法です
となります。それを踏まえた上で考えていきます。
区間スケジューリング問題の特徴としては
- 数直線上で区間をもつタスクが与えられる
- その各タスクがかぶらないように選択し、選択するタスク数を最大化する
という点です。タスクと表現していますが距離のある棒でもいいですし、手の長さでも構いません。区間として見れるものであれば置き換えてください。
タスクの選択方法
貪欲法なので、ルールを決める必要があります。このルールをどう選ぶかが問題です。そして、そのルールは
- 選べるタスクの中で、終了時間が最も早いものを選ぶことを繰り返す
となります。今回のキーエンスプログラミングコンテストを例題に説明します。
キーエンス プログラミング コンテスト 2020 B問題 Robot Arms
問題へのリンク
問題の概要
- 数直線上のXiにロボットiが設置されている
- 数直線上の正負に長さLi腕を伸ばすことができる(Xi-Li と Xi+Liまで伸ばせる)
- 腕が動く範囲が共通部分を持たないようにロボットを取り除ける
- できる限りロボットを残すように選択したい
解法の説明
まず、これがどの様にして区間スケジューリング問題であるかを判断するかです。先程あげた区間スケジューリングの特徴は下記です。
- 数直線上で区間をもつタスクが与えられる
- その各タスクがかぶらないように選択し、選択するタスク数を最大化する
1に関しては、腕の長さを区間と見ることができます。2に関してはまさに問題文がそのとおりになっています。なので、今回はすごくオーソドックスな区間スケジューリング方法であると判断できます。
なので下記ルールに則って確認してみます。対象はAtCoderの問題の例題1を使用します。
- 選べるタスクの中で、終了時間が最も早いものを選ぶことを繰り返す
終了時間が最も早いものから選択対象となるので、Xi - Li と Xi + Li を計算し、 Xi + Liにてソートします。
そして、ソートした後の要素を順に見ていきます。
まず( -2, 6)は最初の要素なので取ることができます。次の要素は開始が最初の要素にかぶっているので取れません。その次はどこにもかぶってないので取ることができます。非常に簡単な例ですが、この様にしていくことで残すロボットを最大化できます。これが区間スケジューリングです。
実装
実装の全体へのリンクを載せます。 github.com
下記実装が、ソートする部分です。
long N = long.Parse(Console.ReadLine()); Tuple<long, long>[] t = new Tuple<long, long>[N]; for (int i = 0; i < N; i++) { long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray(); t[i] = Tuple.Create(input[0] - input[1], input[0] + input[1]); } t = t.OrderBy(x => x.Item2).ToArray();
下記実装が区間スケジューリングの部分です。
long res = 0; long end = int.MinValue; for (int i = 0; i < N; i++) { if (end <= t[i].Item1) { res++; end = t[i].Item2; } } Console.WriteLine(res);
