笔试时间：2025年8月31日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

城市公路某些路段路面质量下降，多多需要对这些路段进行维修。多多可进行工作的时间为1～H。同时有交通管理系统会根据不同因素发出拥堵预警：天气预报显示可能有暴雨、大型活动预计车流剧增、早晚高峰时期等。多多的维修应当在路况不繁忙的时候进行，需要注意预警时段可能存在重叠，比如雨天预警[10,20]和活动预警[15,25]同时存在，则需要避开整个[10,25]时段进行维修。请你帮助多多计算可以进行公路维修的时间共有多少。

输入描述

第一行为一个整数T，表示共有T个测试数据，且1 ≤ T ≤ 10。

每组测试数据:

第一行为一个整数H，表示多多可进行维修的工作总时长，且1 ≤ H ≤ 10⁹。

第二行为一个整数N，表示预警时段的个数，且1 ≤ N ≤ 100000。

接下来的N行，每行输入两个整数xᵢ,yᵢ，表示区域[xᵢ,yᵢ]被预警将有拥堵发生，且1 ≤ xᵢ ≤ yᵢ ≤ H。

输出描述

每组数据输出一个结果，每个结果占一行。

补充说明

对于20%的数据有：1 ≤ H ≤ 10⁶，1 ≤ N ≤ 1000。

对于100%的数据有：1 ≤ H ≤ 10⁹，1 ≤ N ≤ 100000。

样例输入

1

10

2

5 10

5 5

样例输出

4

参考题解

把所有拥堵预警区间做并集，求出被占用的总时长，再用可工作总时长H减去它即可

C++：

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

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

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        long long H;
        int N;
        cin >> H >> N;

        vector<pair<long long, long long>> a(N);
        for (int i = 0; i < N; ++i) {
            long long l, r;
            cin >> l >> r;
            a[i] = {l, r};
        }

        if (N == 0) {
            cout << H << "\n";
            continue;
        }

        sort(a.begin(), a.end()); // 按起点排序（起点相同按终点）

        long long blocked = 0;
        long long L = a[0].first, R = a[0].second;
        for (int i = 1; i < N; ++i) {
            auto [x, y] = a[i];
            if (x <= R) {
                R = max(R, y);
            } else {
                blocked += (R - L + 1);
                L = x; R = y;
            }
        }
        blocked += (R - L + 1);

        cout << (H - blocked) << "\n";
    }
    return 0;
}

Java：

import java.io.*;
import java.util.*;

public class Main {
    static final class FastScanner {
        private final InputStream in;
        private final byte[] buf = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buf[ptr++];
        }
        long nextLong() throws IOException {
            int c; long sgn = 1, val = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) { val = val * 10 + (c - '0'); c = read(); }
            return val * sgn;
        }
        int nextInt() throws IOException { return (int) nextLong(); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int T = fs.nextInt();
        StringBuilder out = new StringBuilder();

        while (T-- > 0) {
            long H = fs.nextLong();
            int N = fs.nextInt();

            long[][] seg = new long[N][2];
            for (int i = 0; i < N; i++) {
                seg[i][0] = fs.nextLong(); // l
                seg[i][1] = fs.nextLong(); // r
            }

            if (N == 0) {
                out.append(H).append('\n');
                continue;
            }

            Arrays.sort(seg, Comparator.comparingLong(s -> s[0]));

            long blocked = 0;
            long L = seg[0][0], R = seg[0][1];
            for (int i = 1; i < N; i++) {
                long x = seg[i][0], y = seg[i][1];
                if (x <= R) {
                    R = Math.max(R, y);
                } else {
                    blocked += (R - L + 1);
                    L = x; R = y;
                }