题目分析与思路提示

1. 核心难点

• 乱序输入：输入的区间并不是按时间先后给出的，我们需要自己整理顺序。
• 合并逻辑：如何高效地判断重叠并更新边界？

2. 算法流程 (贪心 + 排序)

这是解决区间合并问题的标准模板：

1. 存储：使用结构体（或 pair）存储每个区间的左端点 $L$ 和右端点 $R$。
2. 排序：将所有区间按照左端点 $L$ 从小到大排序。这一步至关重要，它保证了我们处理区间时，时间是向后流动的。
3. 遍历与合并：
   • 取出排序后的第 1 个区间，作为当前正在处理的“合并后区间”，记为 $[cur\_L, cur\_R]$。
   • 从第 2 个区间开始遍历（设当前遍历到的区间为 $[next\_L, next\_R]$）：
     • 情况 A（重叠）：如果 $next\_L \le cur\_R$。说明新区间和当前区间有交集（或者刚接上）。
       • 我们需要延长当前区间的右边界：$cur\_R = \max(cur\_R, next\_R)$。
       • 注意：这里要取 max，因为新区间可能被完全包含在旧区间里，比如 [1, 10] 和 [2, 5]，合并后还是 [1, 10]。
     • 情况 B（断开）：如果 $next\_L > cur\_R$。说明出现了一个断层。
       • 当前的编队 $[cur\_L, cur\_R]$ 已经结束了。
       • 统计：编队数量 + 1，计算当前编队的时长，更新最大值。
       • 重置：开始一个新的编队，令 $cur\_L = next\_L, cur\_R = next\_R$。
4. 收尾：循环结束后，别忘了最后一个正在处理的编队还没有被统计进去，需要最后统计一次。

3. 复杂度分析

• 排序：$O(N \log N)$。
• 遍历：$O(N)$。
• 总复杂度：$O(N \log N)$。对于 $N=10^5$，计算量约 $1.7 \times 10^6$，非常轻松。

参考代码 (C++14)

/**
 * 题目：穿越海峡 (Crossing the Strait)
 * 难度：GESP 6级
 * 算法：结构体排序、区间合并
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

// 定义区间结构体
struct Interval {
    int l, r;
};

// 比较函数：按左端点从小到大排序
bool cmp(const Interval &a, const Interval &b) {
    return a.l < b.l;
}

int main() {
    fast_io();

    int N;
    if (!(cin >> N)) return 0;

    vector<Interval> intervals(N);
    for (int i = 0; i < N; ++i) {
        cin >> intervals[i].l >> intervals[i].r;
    }

    // 1. 排序
    sort(intervals.begin(), intervals.end(), cmp);

    // 2. 遍历合并
    int count = 0;
    int max_duration = 0;

    // 初始化当前维护的合并区间
    // 既然 N >= 1，先取第一个
    int cur_l = intervals[0].l;
    int cur_r = intervals[0].r;

    for (int i = 1; i < N; ++i) {
        // 如果当前遍历到的区间起点 <= 维护区间的终点，说明重叠
        if (intervals[i].l <= cur_r) {
            // 合并，右边界取最大值（因为可能只是部分重叠，也可能完全包含）
            cur_r = max(cur_r, intervals[i].r);
        } else {
            // 没有重叠，说明上一个编队结束了
            count++;
            int duration = cur_r - cur_l;
            if (duration > max_duration) {
                max_duration = duration;
            }

            // 开启新的编队
            cur_l = intervals[i].l;
            cur_r = intervals[i].r;
        }
    }

    // 3. 处理最后一个编队
    // 无论如何，最后一个正在维护的 cur_l, cur_r 还没被统计
    count++;
    int duration = cur_r - cur_l;
    if (duration > max_duration) {
        max_duration = duration;
    }

    // 输出结果
    cout << count << " " << max_duration << endl;

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
struct Interval {
    int l, r;
};

bool cmp_gen(const Interval &a, const Interval &b) {
    return a.l < b.l;
}

void solve(int N, vector<Interval> intervals, ofstream& fout) {
    sort(intervals.begin(), intervals.end(), cmp_gen);

    int count = 0;
    int max_duration = 0;
    int cur_l = intervals[0].l;
    int cur_r = intervals[0].r;

    for (int i = 1; i < N; ++i) {
        if (intervals[i].l <= cur_r) {
            cur_r = max(cur_r, intervals[i].r);
        } else {
            count++;
            max_duration = max(max_duration, cur_r - cur_l);
            cur_l = intervals[i].l;
            cur_r = intervals[i].r;
        }
    }
    count++;
    max_duration = max(max_duration, cur_r - cur_l);

    fout << count << " " << max_duration << endl;
}

// 辅助函数
int randRange(int min, int max) {
    if (min > max) return min;
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N;
        vector<Interval> intervals;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 4;
            intervals = {{1,3}, {2,6}, {8,10}, {15,18}};
        }
        else if (i == 2) {
            // 样例2 (乱序+包含+相切)
            N = 5;
            intervals = {{2,4}, {4,8}, {10,12}, {1,3}, {15,20}};
        }
        else if (i == 3) {
            // 完全不重叠 (从小到大)
            N = 100;
            for(int k=0; k<N; k++) {
                int l = k * 10 + 1;
                intervals.push_back({l, l+5});
            }
        }
        else if (i == 4) {
            // 一个巨大的区间包含所有小区间
            N = 100;
            intervals.push_back({1, 10000}); // 大区间
            for(int k=1; k<N; k++) {
                int l = randRange(10, 9000);
                intervals.push_back({l, l + randRange(1, 100)});
            }
        }
        else if (i == 5) {
            // 所有区间都连在一起 (首尾相接)
            N = 1000;
            int current = 1;
            for(int k=0; k<N; k++) {
                int len = randRange(1, 10);
                intervals.push_back({current, current + len});
                current += len; // 下一个起点等于上一个终点
            }
        }
        else if (i == 6) {
            // 完全相同的区间重复多次
            N = 100;
            for(int k=0; k<N; k++) intervals.push_back({10, 20});
        }
        else {
            // 大规模随机 (N=10^5)
            N = 100000;
            // 随机生成起点，长度随机
            // 1/2 概率生成密集重叠，1/2 概率生成稀疏
            int range_scale = (i % 2 == 0) ? 100000 : 10000000; 
            
            for(int k=0; k<N; k++) {
                int l = randRange(1, range_scale);
                int r = l + randRange(1, 1000);
                intervals.push_back({l, r});
            }
        }

        // 打乱顺序 (模拟输入乱序)
        random_shuffle(intervals.begin(), intervals.end());

        // 写入输入
        fin << N << endl;
        for(const auto& item : intervals) {
            fin << item.l << " " << item.r << "\n"; // 使用 \n 加速
        }

        // 写入输出
        solve(N, intervals, fout);

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}