概述

本题给定一天内不重叠的若干任务区间，要求判断是否存在长度至少为 ~s~ 的连续空闲时间段。核心解法是检查相邻任务之间的间隔、起始空闲段和末尾空闲段，取其中最大值与 ~s~ 比较。

分析

核心观察

任务区间互不重叠且按顺序给出（输入保证 ~l_i > r_{i-1}~），因此只需检查任务区间之间的空隙以及一天开头和结尾的空闲时间。

思路

设一天从时刻 ~0~ 开始到时刻 ~m~ 结束。给定 ~n~ 个任务区间 ~(l_i, r_i)~，其中 ~0 \le l_i < r_i \le m~。由于区间不重叠且有序，可能的空闲段包括：

• 从 ~0~ 到第一个任务开始前的空闲段，长度为 ~l_1 - 0 = l_1~。
• 第 ~i~ 个任务结束后到第 ~i+1~ 个任务开始前的空闲段，长度为 ~l_{i+1} - r_i~，其中 ~1 \le i < n~。
• 最后一个任务结束后到 ~m~ 的空闲段，长度为 ~m - r_n~。

若上述任一长度大于等于 ~s~，则 Alex 可以洗澡；否则不能。本题只需判断存在性，不必输出具体方案。

具体示例

以样例第一组 ~n=3, s=3, m=10~，任务为 ~(3,5), (6,8), (9,10)~：起始空闲 ~3~，满足 ~3 \ge 3~，输出 YES。
第二组任务 ~(1,2), (3,5), (6,7)~：起始空闲 ~1 < 3~，中间间隔 ~3-2=1 < 3~，~6-5=1<3~，末尾空闲 ~10-7=3 \ge 3~，输出 YES。
第三组任务 ~(1,2), (3,5), (6,8)~：末尾空闲 ~10-8=2 < 3~，所有间隔均小于 ~3~，输出 NO。

算法步骤

1. 对每个测试用例，读入 ~n, s, m~。
2. 初始化上一个任务结束时间 prev_r = 0（表示一天开始时刻 ~0~）。
3. 设置标志 can = false。
4. 循环读取 ~n~ 个任务区间：
   • 读入当前任务的 ~l_i, r_i~。
   • 检查当前空闲段长度 l_i - prev_r 是否大于等于 ~s~，若是则置 can = true。
   • 更新 prev_r = r_i。
5. 循环结束后，检查末尾空闲段长度 m - prev_r 是否大于等于 ~s~，若是则置 can = true。
6. 若 can 为真输出 YES，否则输出 NO。

复杂度分析

• 时间：每个测试用例 ~O(n)~，所有测试用例的 ~n~ 之和不超过 ~2 \times 10^5~。
• 空间：~O(1)~ 额外空间（不计输入缓存）。

实现注意事项

• 任务区间保证有序且不重叠，无需排序。
• 使用 64 位整数（long long）存储时间值，因为 ~m~ 可到 ~10^9~，但 ~n~ 之和为 ~2e5~，加法仍在 int 范围内，但为安全可用 long long。
• 注意起始空闲段已包含在循环之前的检查中（可将 prev_r 初始化为 ~0~，循环内检查第一个任务前空闲）。
• 末尾空闲段在循环结束后单独检查。

源代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        long long s, m;
        cin >> n >> s >> m;
        long long prev_r = 0;
        bool ok = false;
        for (int i = 0; i < n; ++i) {
            long long l, r;
            cin >> l >> r;
            if (l - prev_r >= s) ok = true;
            prev_r = r;
        }
        if (m - prev_r >= s) ok = true;
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}

import sys

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    idx = 0
    t = int(data[idx]); idx += 1
    out = []
    for _ in range(t):
        n = int(data[idx]); s = int(data[idx+1]); m = int(data[idx+2]); idx += 3
        prev_r = 0
        ok = False
        for _ in range(n):
            l = int(data[idx]); r = int(data[idx+1]); idx += 2
            if l - prev_r >= s:
                ok = True
            prev_r = r
        if m - prev_r >= s:
            ok = True
        out.append("YES" if ok else "NO")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()