Moe's CF Life

喵哈~！各位算法爱好者们，大家好呀！人家是你们的小助教猫娘，今天也要元气满满地和大家一起学习算法哦！( ´ ▽ ` )ﾉ

今天我们要看的是一道非常经典的区间问题，叫做 "Nested Segments"。别看它名字好像有点吓人，其实只要找到正确的思路，就像猫咪找到最舒服的纸箱一样简单哦！那么，就让本猫娘带你一步步拆解这个问题吧~

题目大意

这道题是说，我们收到了 n 个一维线段，每个线段都有一个左端点 l 和一个右端点 r，表示为 [l, r]。我们的任务呢，就是在这 n 个线段中，找到两个不同的线段，比如说线段 i 和线段 j，使得线段 i 完全包含在线段 j 内部。

什么样的才算“完全包含”呢？喵~，就是说线段 i 的左端点要大于等于线段 j 的左端点，同时线段 i 的右端点要小于等于线段 j 的右端点。用数学语言表达就是：li ≥ lj 并且 ri ≤ rj。

如果能找到这样的一对线段，我们就输出它们原来的编号 i 和 j。如果有很多对符合条件，随便输出一对就可以啦。如果找遍了也找不到，那就说明没有这样的线段对，我们就输出 -1 -1。

举个栗子：线段 A 是 [2, 9]，线段 B 是 [1, 10]。因为 2 ≥ 1 并且 9 ≤ 10，所以线段 A 就被线段 B 包含啦！

题解方法

直接一个一个比较（暴力枚举）肯定是不行的啦，n 最大有 30 万，O(n²) 的复杂度会让电脑过热的，就像夏天没开空调的猫窝一样，喵呜... >w<

所以，我们需要一个更聪明的办法！

问题的关键在于这两个条件：li ≥ lj 和 ri ≤ rj。这种带有大小比较的问题，我们的第一反应通常是——排序！

那么，要怎么排序呢？

我们可以先尝试满足第一个条件 li ≥ lj。如果我们把所有线段都按照左端点 l 从小到大排序，会发生什么奇妙的事情呢？

当排好序后，我们从头到尾遍历这些线段。对于任意一个线段 current，它前面的所有线段 previous 的左端点 l 都一定小于等于 current 的左端点 l。也就是说，current.l ≥ previous.l 这个条件天然就满足了！

这样一来，问题就简化了！我们只需要在遍历的时候，对于当前的线段 current，看看在它之前的线段中，是否存在一个 previous，使得 current.r ≤ previous.r。

但是，难道我们要把前面所有的 previous 都检查一遍吗？那不又变回 O(n²) 了嘛！当然不是啦~

我们只需要一个“最有可能”成为包含者的线段就好了。什么样的线段最有可能包含其他线段呢？当然是右端点尽可能大的线段啦！

于是，我们的最终策略就诞生了喵！

预处理：因为最后要输出原始编号，所以我们需要一个结构体（struct）来把每个线段的 l, r 和它的原始编号 id 捆绑在一起。
排序：这是最最关键的一步！我们自定义一个排序规则：
- 主要按左端点 l 从小到大排序。
- 如果左端点 l 相同，就按右端点 r 从大到小排序。
- （思考一下为什么 r 要从大到小排：如果两个线段左端点相同，[l, r1] 和 [l, r2]，假设 r1 > r2，那么 [l, r2] 肯定被 [l, r1] 包含。按 r 降序排，[l, r1] 就会在 [l, r2] 前面，我们处理 [l, r2] 的时候就能立刻发现它被前面的包含了，非常方便！）
贪心遍历：
- 我们用两个变量 max_r 和 max_r_id 来记录我们到目前为止遇到的所有线段中，那个拥有最大右端点的线段的 r 值和 id。
- 我们从排序后的第二个线段开始遍历（第一个线段作为初始的 max_r）。
- 对于当前遍历到的线段 segments[i]，由于我们的排序规则，segments[i].l 肯定大于等于 max_r 所在线段的 l。
- 所以，我们只需要比较它们的右端点！如果 segments[i].r <= max_r，那么恭喜！我们找到了！被包含的线段是 segments[i]，包含它的线段是 id 为 max_r_id 的那个。直接输出 segments[i].id 和 max_r_id，然后就可以结束程序啦。
- 如果 segments[i].r > max_r，说明当前的 segments[i] 没有被之前的“最强者”包含。不过，它自己可能成为一个新的“最强者”，因为它有更大的右端点，可能会包含后面的线段。所以，我们就更新 max_r = segments[i].r 和 max_r_id = segments[i].id。
处理未找到的情况：如果整个循环跑完了都没有找到，就说明不存在这样的线段对，输出 -1 -1。

这个方法的时间复杂度主要是排序的 O(n log n)，遍历是 O(n)，所以总的就是 O(n log n)，对于 30 万的数据量来说，是完全没问题的！完美，喵~

题解

下面就是这份思路的 C++ 实现啦，人家加上了中文注释，方便大家理解哦！

cpp

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

// 用一个结构体来保存线段的信息，包括左端点、右端点和原始编号
// 这样排序后就不会丢失原始信息啦，喵~
struct Segment {
    int l, r, id;
};

int main() {
    // 加速一下输入输出，让程序跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    // 如果只有一个线段，肯定找不到一对呀
    if (n < 2) {
        std::cout << "-1 -1\n";
        return 0;
    }

    // 创建一个vector来存放所有的线段
    std::vector<Segment> segments(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> segments[i].l >> segments[i].r;
        segments[i].id = i + 1; // 题目要求编号从1开始
    }

    // 最关键的一步：排序！
    // 使用 lambda 表达式来自定义排序规则
    std::sort(segments.begin(), segments.end(), [](const Segment& a, const Segment& b) {
        // 首先，按左端点 l 从小到大排序
        if (a.l != b.l) {
            return a.l < b.l;
        }
        // 如果左端点相同，按右端点 r 从大到小排序
        return a.r > b.r;
    });

    // 记录到目前为止遇到的右端点最大的线段的信息
    int max_r = segments[0].r;
    int max_r_id = segments[0].id;

    // 从第二个线段开始遍历
    for (int i = 1; i < n; ++i) {
        // 因为已经排过序，左端点的条件 (segments[i].l >= l_of_max_r_segment) 是天然满足的
        // 所以我们只需要检查右端点
        if (segments[i].r <= max_r) {
            // 找到了！当前线段被之前的 max_r 线段包含了
            // 输出它们的原始编号然后结束程序
            std::cout << segments[i].id << " " << max_r_id << "\n";
            return 0;
        }

        // 如果当前线段没有被包含，并且它的右端点更大
        // 那么它就成为了新的“最有可能包含别人的”线段
        // 更新 max_r 和 max_r_id
        if (segments[i].r > max_r) {
            max_r = segments[i].r;
            max_r_id = segments[i].id;
        }
    }

    // 如果循环结束了还没找到，说明不存在这样的线段对
    std::cout << "-1 -1\n";

    return 0;
}

知识点介绍

这道题虽然不难，但涉及到的知识点可是非常实用的哦！

贪心算法 (Greedy Algorithm) 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。在这道题里，我们的“贪心”选择是：在遍历时，始终只将当前线段与“目前为止右端点最大的线段”进行比较。我们相信这个局部最优的选择（和最强的比）能帮我们最快地找到答案。
自定义排序 (Custom Sorting) 标准库的 std::sort 函数非常强大，它不仅能对数字、字符串等进行默认排序，还可以接受第三个参数——一个比较函数（或称为比较器），来让我们定义自己的排序逻辑。题解中使用的 Lambda 表达式 [](...){...} 是 C++11 引入的一种编写匿名函数的简洁方式，非常适合用在这里。掌握自定义排序，你就可以让任何数据结构按照你的心意来排列啦！
结构体 (Struct) 当我们需要把几个不同类型但逻辑上相关的变量（比如线段的 l, r, id）打包在一起时，使用 struct 是一个绝佳的选择。它能让我们的代码更清晰，更有条理。特别是在排序时，将原始信息（如 id）和排序依据（如 l, r）绑定在一起，可以有效防止信息丢失，是非常重要的技巧。

好啦，今天的讲解就到这里啦！希望大家都能理解并掌握这个问题的解决方法。以后遇到类似的区间问题，记得要先想一想排序能不能帮上忙哦！我们下次再见，喵~ (ฅ'ω'ฅ)

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍