いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題ですね。
問題概要
個の仕事があって、仕事 は、 の時間を要し、時刻 までに終わらなければならない。
時刻 0 に仕事を開始する。 個の仕事をすべて完遂することが可能かどうかを判定せよ。
制約
考察
直感的には、締め切りが早いものから順にやっていくべきなようにも思えます。それが実際正しいことを、順を追って確認していきましょう。
「交換しても悪化しない」を考える
まずあらゆる仕事のうち、締め切りが最も早い仕事を としましょう (締め切り時刻を 、作業時間を とします)。
この仕事 が最初に行われないような解で「締め切り違反をしない」ものがあったとしましょう。このとき、この「締め切り違反をしない」という性質を崩すことなく、仕事 を先頭へと持って来れることを示しましょう。
その解において、仕事 の直前の仕事を としましょう。このとき、 と を入れ替えても、締め切り違反はしません。なぜなら、次のように考えられるからです。
- 入れ替えたあとに作業 が終了する時刻は、今までよりむしろ早くなるので、作業 を先にやっても締め切りを超えません
- 入れ替えたあとに作業 が終了する時刻は、現状の「作業 が終了する時刻」と同じになります (入れ替えただけなので)。作業 の締め切りは作業 の締め切りよりも後ろにありますので、問題ありません
同様に入れ替えを繰り返すことで、作業 を先頭に持ってくることができます。以後同様に、締め切りが早い順に前に持ってくることができます。
コード
計算量は となります (ソートに要する計算量です)。
#include <iostream> #include <vector> #include <algorithm> using namespace std; // (所要時間, 締め切り) のペア using pll = pair<long long, long long>; int main() { // 入力 int N; cin >> N; vector<pll> v(N); for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second; // 締め切りが早い順にソート sort(v.begin(), v.end(), [&](pll a, pll b) {return a.second < b.second;}); // 締め切りが早い順に仕事をこなしていく bool ok = true; long long time = 0; for (int i = 0; i < N; ++i) { time += v[i].first; if (time > v[i].second) ok = false; } // 出力 if (ok) cout << "Yes" << endl; else cout << "No" << endl; }
必要条件を列挙する考え方
他の考え方もしてみましょう。まずは当然満たすべきこととして、
時刻 が締め切りの仕事があったとき、時刻 以前に締め切りのある仕事は、時刻 までに終わらなければならない
ということがいえます。そして、実はこの必要条件は十分条件でもあることがいえます。つまり、この条件さえ満たしていれば、仕事を完遂することができるのです。
具体的には、上の条件を満たしているとき、次に示すアルゴリズムによって、仕事を完遂することができるのです
- 締め切りの時刻が早い順に仕事をソートして
- その順序で仕事を順にやっていき
- 終了時刻が締め切り後になる箇所が発生したらダメです
- 発生しなければ実際にすべての仕事を完遂できています
これはまさに、上で述べた貪欲解法に他なりません。