给定 \(N\) 个闭区间 \([l_i,r_i]\)，要求将所有有交集（包括端点重合）的区间进行合并，最终计算出合并后互不相交的区间集合。
处理区间问题的核心往往在于消除无序性，如果区间是散乱分布的，很难判断一个区间究竟会与哪些区间发生合并。
通过将所有区间按照左端点从小到大进行排序，问题就会展现出明显的单调性。当从左到右依次处理排序后的区间时，任何一个新区间与当前维护的合并区间，只可能存在以下三种空间相对关系：
情况 1：完全包含（新区间在当前区间内部）
当前维护: [===================]
新区间: [========]
处理：无须任何操作，右端点保持不变。
情况 2：交集相交（新区间延伸了当前区间）
当前维护: [===================]
新区间: [==============]
处理：更新当前区间的右端点为新区间的右端点。
情况 3：完全脱离（两个区间无交集）
当前维护: [===================]
新区间: [========]
处理：当前维护的区间已经不可能再向右延伸。将其存入答案，并以新区间作为起点开始维护。
有 \(n\) 个线段，每一个线段用 \([a_i, b_i]\) 表示，求所有线段的并集的总长度。
数据范围：\(n \le 20000, \ -2^{31} \le a_i \le b_i \le 2^{31}\)，且 \(a_i\) 和 \(b_i\) 都是整数。
考虑两个有交集的线段，左端点靠左的那个是 \([a_1, b_1]\)，另一个是 \([a_2, b_2]\)，因为假定了 \(a_2 \ge a_1\)，所以总的长度取决于 \(b_1\) 和 \(b_2\) 的关系。如果 \(b_2 \le b_1\)，那么第二个线段被第一个线段完全包含，合并后线段的左右端点和靠左的线段一模一样；如果 \(b_2 > b_1\)，则相当于左端点不变的情况下，右端点在向右延展。
所以可以得到一个解法：将所有线段按左端点从小到达排序，如果相邻两个线段有交集，按上面的规则更新当前正在处理的线段的左右端点；如果相邻两个线段没有交集，则统计前面那个整体线段的长度，并将新的这个线段作为当前正在处理的线段。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 20005;
struct Fire {
int l, r;
};
Fire a[N];
int main()
{
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].r);
// 按左端点排序
sort(a + 1, a + n + 1, [](Fire f1, Fire f2) {
return f1.l < f2.l;
});
int ans = 0, bg = a[1].l, ed = a[1].r; // 目前处理的燃烧段是[bg,ed]
for (int i = 2; i <= n; i++) {
if (a[i].l <= ed) ed = max(ed, a[i].r); // 与当前段有交叉
else { // 与当前段无交叉
// 答案加上上一段的燃烧总长，并将新的燃烧段端点设为a[i]的两个端点
ans += ed - bg; bg = a[i].l; ed = a[i].r;
}
}
ans += ed - bg; // 不要忘了处理最后一段
printf("%d\n", ans);
return 0;
}
这道题的目标是计算多个时间段合并后的“最长连续工作时间”和“最长连续空闲时间”，是一个经典的区间合并问题。
有一堆表示工作时间的区间 \([l,r]\)，当多个区间有重叠时，它们可以被视为一个更长的、连续的工作时间段。例如 \([300,1000]\) 和 \([700,1200]\) 重叠，可以合并成一个大的连续工作段 \([300,1200]\)。需要找到所有这样合并后形成的连续工作段中，最长的一个。同时，也需要找到这些合并后的连续工作段之间的空隙（无人工作时间），并找出其中最长的一个。
首先，将所有的区间（工作时段）按照它们的左端点（开始时间）从小到大排序。这是至关重要的一步，它保证了处理区间时是按照时间顺序向前推进的。
初始化一个“当前合并区间” \([bg,ed]\)，它的值最初等于第一个（排序后）工作时段。对于接下来的每个工作时段 \(a_i\)，有两种情况需要考虑。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5005;
struct Work { // 定义工作时段结构体
int l, r; // l：开始时间，r：结束时间
};
Work a[N]; // 结构体数组，存储所有工作时段
int main()
{
int n;
scanf("%d", &n); // 读取农民（工作时段）的数量
for (int i = 1; i <= n; i++) { // 循环读取 n 个工作时段
scanf("%d%d", &a[i].l, &a[i].r);
}
// 1. 将所有的工作时段按开始时间（左端点）从小到大排序
sort(a + 1, a + n + 1, [](Work w1, Work w2) {
return w1.l < w2.l;
});
// 2. 合并与计算
int bg = a[1].l, ed = a[1].r; // [bg,ed]为当前正在工作的时段，刚开始等于第一个时间段
int ans1 = ed - bg, ans2 = 0; // ans1为最长连续工作时间，ans2为最长连续空闲时间
for (int i = 2; i <= n; i++) { // 从第二个工作时段开始遍历
if (a[i].l <= ed) { // 说明a[i]这个工作时段与当前正在工作的时间段有交叉
ed = max(ed, a[i].r); // 更新合并区间的结束时间，取两者中更晚的那个
ans1 = max(ans1, ed - bg); // 可能需要更新最长连续工作时长
} else { // 与正在工作的时间段没有交叉，出现空隙
ans2 = max(ans2, a[i].l - ed); // 计算刚刚结束的空闲时段的长度，并更新最长空闲时间
bg = a[i].l; ed = a[i].r; // 重置合并区间，开始一个新的连续工作段
ans1 = max(ans1, ed - bg); // 可能需要更新最长连续工作时长
}
}
printf("%d %d\n", ans1, ans2); // 输出最终结果
return 0;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。