YoppinWork [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 B]

前提知識

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

解説

https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/yoppinwork/submissions/code/1316764099

この問題は、区間スケジューリング問題と呼ばれるものである。
区間スケジューリング問題では、終了時刻が早い仕事を貪欲に取ってくれば最適解が得られる。
終了時刻でソートし、とっていこう。
{終了時刻, 開始時刻}とpairでvectorに入れておき、ソートする。

int T, N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> T >> N;
    vector<pair<int, int>> v;
    rep(i, 0, N) {
        int a, b;
        cin >> a >> b;
        v.push_back({b, a});
    }
    sort(all(v));

    int ans = 0, t = 0;
    fore(p, v) {
        if (t <= p.second) {
            ans++;
            t = p.first;
        }
    }
    cout << ans << endl;
}