いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題ですね。

問題概要

$N$ 個の仕事があって、仕事 $i$ は、 $A_i$ の時間を要し、時刻 $B_i$ までに終わらなければならない。

時刻 0 に仕事を開始する。 $N$ 個の仕事をすべて完遂することが可能かどうかを判定せよ。

制約

$1 \le N \le 2 \times 10^{5}$

考察

直感的には、締め切りが早いものから順にやっていくべきなようにも思えます。それが実際正しいことを、順を追って確認していきましょう。

「交換しても悪化しない」を考える

まずあらゆる仕事のうち、締め切りが最も早い仕事を $P$ としましょう (締め切り時刻を $p$ 、作業時間を $a$ とします)。

この仕事 $P$ が最初に行われないような解で「締め切り違反をしない」ものがあったとしましょう。このとき、この「締め切り違反をしない」という性質を崩すことなく、仕事 $P$ を先頭へと持って来れることを示しましょう。

その解において、仕事 $P$ の直前の仕事を $Q$ としましょう。このとき、 $Q$ と $P$ を入れ替えても、締め切り違反はしません。なぜなら、次のように考えられるからです。

入れ替えたあとに作業 $P$ が終了する時刻は、今までよりむしろ早くなるので、作業 $P$ を先にやっても締め切りを超えません
入れ替えたあとに作業 $Q$ が終了する時刻は、現状の「作業 $P$ が終了する時刻」と同じになります (入れ替えただけなので)。作業 $Q$ の締め切りは作業 $P$ の締め切りよりも後ろにありますので、問題ありません

同様に入れ替えを繰り返すことで、作業 $P$ を先頭に持ってくることができます。以後同様に、締め切りが早い順に前に持ってくることができます。

コード

計算量は $O(N \log N)$ となります (ソートに要する計算量です)。

#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;
}

必要条件を列挙する考え方

他の考え方もしてみましょう。まずは当然満たすべきこととして、

時刻 $t$ が締め切りの仕事があったとき、時刻 $t$ 以前に締め切りのある仕事は、時刻 $t$ までに終わらなければならない

ということがいえます。そして、実はこの必要条件は十分条件でもあることがいえます。つまり、この条件さえ満たしていれば、仕事を完遂することができるのです。

具体的には、上の条件を満たしているとき、次に示すアルゴリズムによって、仕事を完遂することができるのです

締め切りの時刻が早い順に仕事をソートして
その順序で仕事を順にやっていき
- 終了時刻が締め切り後になる箇所が発生したらダメです
- 発生しなければ実際にすべての仕事を完遂できています

これはまさに、上で述べた貪欲解法に他なりません。

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 131 D - Megalomania (茶色, 400 点)

問題概要

制約

考察

「交換しても悪化しない」を考える

コード

必要条件を列挙する考え方