解题思路

• 裁剪到工作范围：只保留与 $[1, H]$ 相交的区间，并将其裁剪到该范围内。
• 排序并合并：按左端点排序，依次合并所有重叠或相邻的区间（即 $l \le r_{\text{cur}} + 1$ 时合并）。
• 求覆盖长度：合并后各段长度相加（闭区间长度为 $r-l+1$），得到 $U$。
• 最终答案：$\text{ans} = H - U$，若无区间则 $\text{ans} = H$。
• 复杂度：排序主导，时间 $O(N \log N)$，空间 $O(1)$ 额外（不计输入存储）。

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>> segs;
		segs.reserve(N);

		for (int i = 0; i < N; ++i) {
			long long x, y;
			cin >> x >> y;
			// 保障左右端点有序
			if (x > y) swap(x, y);
			// 裁剪到 [1, H]
			x = max(x, 1LL);
			y = min(y, H);
			if (x <= y) segs.emplace_back(x, y);
		}

		if (segs.empty()) {
			cout << H << "\n"; // 没有覆盖，答案为 H
			continue;
		}

		sort(segs.begin(), segs.end()); // 按左端点排序

		long long covered = 0;
		long long curL = segs[0].first, curR = segs[0].second;

		for (size_t i = 1; i < segs.size(); ++i) {
			long long l = segs[i].first, r = segs[i].second;
			// 合并重叠或相邻的闭区间：l <= curR + 1
			if (l <= curR + 1) {
				curR = max(curR, r);
			} else {
				covered += (curR - curL + 1);
				curL = l; curR = r;
			}
		}
		covered += (curR - curL + 1);

		long long ans = H - covered;
		if (ans < 0) ans = 0; // 稳妥处理
		cout << ans << "\n";
	}
	return 0;
}

Python

import sys

def solve():
	data = list(map(int, sys.stdin.buffer.read().split()))
	it = iter(data)
	try:
		T = next(it)
	except StopIteration:
		return
	out = []
	for _ in range(T):
		H = next(it)
		N = next(it)
		segs = []
		for _ in range(N):
			x = next(it); y = next(it)
			if x > y:
				x, y = y, x
			# 裁剪到 [1, H]
			x = max(x, 1)
			y = min(y, H)
			if x <= y:
				segs.append((x, y))
		if not segs:
			out.append(str(H))
			continue
		segs.sort()
		covered = 0
		curL, curR = segs[0]
		for l, r in segs[1:]:
			# 合并重叠或相邻闭区间
			if l <= curR + 1:
				if r > curR:
					curR = r
			else:
				covered += (curR - curL + 1)
				curL, curR = l, r
		covered += (curR - curL + 1)
		ans = H - covered
		if ans < 0:
			ans = 0
		out.append(str(ans))
	sys.stdout.write("\n".join(out))

if __name__ == "__main__":
	print() if False else solve()

Java

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

/** 合并区间并计算未覆盖总长度 */
public class Main {
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = 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(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		long nextLong() throws IOException {
			int c; do { c = read(); } while (c <= ' ' && c != -1);
			boolean neg = false;
			if (c == '-') { neg = true; c = read(); }
			long val = 0;
			while (c > ' ') {
				val = val * 10 + (c - '0');
				c = read();
			}
			return neg ? -val : val;
		}
		int nextInt() throws IOException { return (int) nextLong(); }
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		StringBuilder sb = new StringBuilder();
		int T;
		try {
			T = fs.nextInt();
		} catch (Exception e) {
			return;
		}
		while (T-- > 0) {
			long H = fs.nextLong();
			int N = fs.nextInt();
			List<long[]> segs = new ArrayList<>(N);
			for (int i = 0; i < N; i++) {
				long x = fs.nextLong(), y = fs.nextLong();
				if (x > y) { long t = x; x = y; y = t; }
				// 裁剪到 [1, H]
				if (y < 1 || x > H) continue;
				x = Math.max(x, 1L);
				y = Math.min(y, H);
				if (x <= y) segs.add(new long[]{x, y});
			}
			if (segs.isEmpty()) {
				sb.append(H).append('\n');
				continue;
			}
			segs.sort(Comparator.comparingLong(a -> a[0]));

			long covered = 0;
			long curL = segs.get(0)[0], curR = segs.get(0)[1];
			for (int i = 1; i < segs.size(); i++) {
				long l = segs.get(i)[0], r = segs.get(i)[1];
				// 合并重叠或相邻闭区间
				if (l <= curR + 1) {
					if (r > curR) curR = r;
				} else {
					covered += (curR - curL + 1);
					curL = l; curR = r;
				}
			}
			covered += (curR - curL + 1);

			long ans = H - covered;
			if (ans < 0) ans = 0;
			sb.append(ans).append('\n');
		}
		System.out.print(sb.toString());
	}
}

题目内容

城市公路某些路段路面质量下降，多多需要对这些路段进行维修。多多可进行工作的时间为 $1$～$H$ 。

同时有交通管理系统会根据不同因素发出拥堵预警：天气预报显示可能有暴雨、大型活动预计车流剧增、早晚高峰时期等。

多多的维修应当在路况不繁忙的时候进行，需要注意预警时段可能存在重叠，比如雨天预警 $[10,25]$ 和活动预警 $[15,25]$ 同时存在，则需要避开整个 $[10,25]$ 时段进行维修

请你帮助多多计算可以进行公路维修的时间共有多少

输入描述

第一行为一个整数 $T$ ,表示共有 $T$ 个测试数据 $(1<= T<= 10)$

每组测试数据：

第一行为一个整数 $H$ ，表示多多可进行维修的工作总时长 $(1 <= H <= 10^9)$

第二行为一个整数 $N$ ，表示预警时段的个数 $(1<=N<= 100000)$

接下来的 $N$ 行：

每行输入两个整数 $xi,yi$ , 表示区域 $[xi,yi]$ 被预警将有拥堵发生 $(1 <= xi <= yi<= H)$

输出描述

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

补充说明

对于 $20$% 的数据有：$1<=H<= 10^6,1 <= N <= 1000$

对于 $100$% 的数据有：$1<=H<= 10^9,1 <=N <= 100000$

样例1

输入

1
10
2
5 10
5 5

输出

4

说明

多多仅能在 $1$ ~ $4$ 的时间段内进行维修，工作时长为 $4$

样例2

输入

1
3
1
1 3

输出

0

说明

多多的工作时间内全是拥堵预警，无法进行维修

样例3

输入

1
5
2
1 2
4 5

输出

1

说明

多多仅能在$3$~$3$的时间段内进行维修，工作时长为$1$