uniform linear sushi [OyamaC]

https://www.hackerrank.com/contests/oyamac/challenges/uniform-linear-sushi

前提知識

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

解説

https://www.hackerrank.com/contests/oyamac/challenges/uniform-linear-sushi/submissions/code/1321978723

ある寿司を食べている時間は、[S, S+T]の区間の時間となる。
このように区間として考えると、今回の問題は区間スケジューリング問題と全く同じになる。
よって、終了時間が早い寿司から順に取っていく貪欲法で解こう。

これはvector<pair<int,int>>に{S+T,S}を入れてソートすればいい。
vector,pairのソートは最初の要素の昇順、同じなら、次の要素の昇順でやってくれるので、
これで区間の右端が小さい順から取得できる。
あとは、現在時刻を持ちながら貪欲に選択していけばいい。

int N;
vector<pair<int, int>> ST;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int s, t; cin >> s >> t;
        int L = s, R = s + t;
        ST.push_back({ R, L });
    }
    sort(all(ST));

    int ans = 0;
    int cur = 0;
    fore(p, ST) {
        int L = p.second;
        int R = p.first;

        if (cur <= L) {
            cur = R;
            ans++;
        }
    }
    cout << ans << endl;
}