予約システム [パソコン甲子園2017 予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0360?year=2017

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0360/review/3136426/hamayanhamayan/C++14

この問題では半開区間で区間が表現されているが、閉区間に直して解くことにする。
区間についてはここが詳しい
N個すべての区間について[a,b]と重なるかどうかを判定する。
重なるかの判定がすこしやりにくいので、重なっていないかを判定することにする。
区間[a,b]と区間[s,f]が重なっていないのは、b＜sまたはf＜aを満たす場合である。
b＜sとなるのは[a,b],[s,f]の順で区間が並んでいる状態である。
f＜aとなるのは[s,f],[a,b]の順で区間が並んでいる状態である。
重なっていないならば、continueをして次の区間を見る。
重なっていれば1と出力して終了。
　
なお、この問題はimos法を用いても解ける。
imos法の練習問題としても良いだろう。

int a, b, N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> a >> b >> N; b--;
    rep(i, 0, N) {
        int s, f; cin >> s >> f; f--;
        if (b < s) continue;
        if (f < a) continue;
        printf("1\n");
        return;
    }
    printf("0\n");
    return;
}