Double Booking [第七回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202107-open/tasks/past202107_f

解説

https://atcoder.jp/contests/past202107-open/submissions/24465658

判定を効率化する問題。
大変そうに見えるが、特に大きなひねりはなく、愚直に実装すれば間に合う。
慣れている人はimos法が思い浮かぶかと思うが、実際は必要ない。
（必要ないが、使えばそこそこ早くなる）

日付毎に判定していく

今回は、日付をまたいだ予定というのはない。
なので、日付毎に予定が被っているかを判定して、一つでもかぶっていればyesだし、1つもないならnoである。

まずは日付毎に予定を分ける作業が必要であるが、自分はこの部分をmapにvectorを載せることで実現した。

days[d] := d日目の予定であり、{開始時間,終了時間}の集合

というデータ構造を用意することにする。
ここで、{開始時間,終了時間}としているが、開始時間と終了時間が同じでも時間としてはかぶっていないように考えるので、
半開区間、つまり、「開始時間≦hour＜終了時間」、記号的には「[開始時間,終了時間)」のように考えることにする。
競技プログラミングではこのように半開区間にすると色々扱いやすい場合が多い。（慣れかもしれないけど）

このデータ構造が作れれば、イテレータで日付別に取り出せるので、各日について重複判定をして、重複しているならyesとする。

重複判定

日付はもう関係ないので、区間の集合があったときに重複しているかをcheckDuplication関数で判定していく。
区間が0～24の範囲しかないので、適当に実装すれば間に合う。
具体的には以下のような配列を用意して、使用されている区間を数え上げていく。

book[h] := 時間hが予約されている件数

普通にループで件数を足していき、最後に2件以上予約されていれば、被っていることになる。
これでAC。

int N, D[101010], S[101010], T[101010];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
bool checkDuplication(vector<pair<int, int>> ranges) {
    vector<int> booked(24);
    fore(range, ranges) rep(h, range.first, range.second) booked[h]++;
    rep(h, 0, 24) if (1 < booked[h]) return true;
    return false;
}
//---------------------------------------------------------------------------------------------------
string solve() {
    map<int, vector<pair<int, int>>> days;
    rep(i, 0, N) days[D[i]].push_back({ S[i], T[i] });

    fore(p, days) if (checkDuplication(p.second)) return yes;
    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> D[i] >> S[i] >> T[i];
    cout << solve() << endl;
}