https://www.hackerrank.com/contests/oyamac/challenges/uniform-linear-sushi
前提知識
- 区間スケジューリング問題
解説
ある寿司を食べている時間は、[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; }