题解 | #聊天# 暴力模拟

依次增加起床时间，将B的空闲时间不断后移，每次增加后判断是否与A的空闲时间相交

#include <iostream>
#include <vector>
using namespace std;

// 判断两个时间段是否相交
bool isIntersect(pair<int, int> a, pair<int, int> b) {
    if (a.first <= b.first && a.second <= b.second && a.second >= b.first) {
        return true;
    }
    if (b.first <= a.first && b.second <= a.second && b.second >= a.first) {
        return true;
    }
    return false;
}

int main() {
    int p, q, l, r;
    while (cin >> p >> q >> l >> r) {
        vector<pair<int, int>> atime(p);
        vector<pair<int, int>> btime(q);
        for (int i = 0; i < p; i++) {
            cin >> atime[i].first >> atime[i].second;
        }
        for (int i = 0; i < q; i++) {
            cin >> btime[i].first >> btime[i].second;
        }
        int ans = 0; // 返回答案
        bool flag = false; // 标志是否找到相交
        for (int i = l; i <= r; i++) {
            auto tmp = btime; // 每次最外层循环复制一份，避免原数据被改写
            // 把B的所有空闲时间都增加相应的起床时刻值
            for (int j = 0; j < q; j++) {
                tmp[j].first += i;
                tmp[j].second += i;
            }
            // 两两遍历a和b的所有空闲时间，判断是否相交
            for (int m = 0; m < p; m++) {
                flag = false;
                for (int n = 0; n < q; n++) {
                    if (isIntersect(atime[m], tmp[n])) {
                        ans++;
                        flag = true;
                        break;
                    }
                }
                // 找到一组相交的就提前跳出
                if (flag) {
                    break;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

时间复杂度：最耗时的操作是双重循环，其中外层循环遍历了时间段 [l, r] 中的每一个时间点，内层循环遍历了两个人的所有空闲时间段，因此时间复杂度为 O((r-l+1) * p * q)，其中 p 和 q 分别表示两个人的空闲时间段数

空间复杂度：使用了两个 vector，分别存储了两个人的空闲时间段，因此空间复杂度为 O(p+q)