典型アルゴリズム問題集 B問題（区間スケジューリング問題）を解く

AtCoder で公開されている「典型アルゴリズム問題集」のB問題をC++で解いてみました。

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

問題はリンク先をご覧ください。

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

区間スケジューリング問題を紹介します。終わる順番が早い順に処理するという貪欲法になります。

解答案

時間的に重複して対応することができない一連のタスクについて、どのように処理すればよいでしょうか。以下が候補です。

• タスクが始まる時間が早い順番に処理する。
• タスクの時間が短い順番に処理する。
• タスクが終わる時間が早い順番に処理する。

タスクをすべて同じ価値と考えると、どのような場合に一番多くのタスクが処理できるでしょうか。この場合、「タスクが終わる時間が早い順番に処理する」ことで一番多くのタスクが処理できます。

異なる方法を選んでも、それより結果が良くならないことで示せます。

C++ プログラム例

タスクが始まる日にち $A_i$ と終わる日にち $B_i$ を読み込みます。次に、終わる日にちが早い順番にソートします（17ー21行目）。

現在の日にちを now とします。タスクが終わる日にちが早い順番に以下の手順で処理します。

• now $\leqq A_i$ であれば、そのタスクを処理する。
• now を $B_i + 1$ に更新する。

以下が、C＋＋プログラムとなります。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	vector<pair<int, int>> p(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		p[i] = make_pair(b[i], a[i]);
	}
	sort(p.begin(), p.end());
	for (int i = 0; i < n; ++i) {
		a[i] = p[i].second;
		b[i] = p[i].first;
	}

	int result = 0;
	int now = 0;
	for (int i = 0; i < n; ++i) {
		if (now <= a[i]) {
			++result;
			now = b[i] + 1;
		}
	}

	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

「区間スケジューリング問題」と知られている問題を解いてみました。貪欲法でうまく行く問題です。

この問題集は、わたくしには、ちょうど良い難易度でした。解答案を紹介していきます。