区间合并（超详细逐步讲解/例题/思路分析/参考代码）

区间合并超详解

• 区间合并是什么？
• 例1
• • 问题描述
  • 输入
  • 输出
  • 数据规模
  • 输入输出
  • • 思路分析
    • 代码
    • 例2
    • • 问题描述
      • 输入
      • 输出
      • 数据规模
      • 输入输出
      • • 思路分析
        • 代码
        • 例3
        • • 问题描述
          • 输入
          • 输出
          • 输入输出
          • • 思路分析
            • 代码
            • 例4
            • • 问题描述
              • 输入
              • 输出
              • 输入输出
              • • 参考代���

                  区间合并是什么？

                  我们要了解区间合并是什么，首先来看这样的一个例子。

                  区间2是区间1的一个子区间

                  区间3和区间1有交集

                  区间4和区间1端点在同一个点上

                  区间5和区间1没有交集

                  所以区间2,3，4都可以和区间1合并形成一个新的区间，区间5则不行。

                  总结：区间合并就是把多个区间有交集的部分，快速进行合并。

                  接下来我们通过一个例子来快速体验一下区间合并

                  例1

                  问题描述

                  给定2个闭区间 [a1,b1],[a2,b2]，判断这两个区间能否合并成为一个新的区间。

                  任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1,2] 和 [2,3] 可以合并为[1,3] ；[1,3] 和 [2,4] 可以合并为 [1,4]，但是 [1,2] 和 [3,4] 不可以合并。

                  我们的任务是判断这两个区间是否可以最终合并为一个闭区间，如果可以，输出 Yes，否则输出 No。

                  输入

                  一共两行。

                  第一行两个整数a1,b1 ，表示第一个区间。

                  第二行两个整数 a2,b2，表示第二个区间。

                  输出

                  两个区间是否可以最终合并为一个闭区间，如果可以，输出 Yes，否则输出 No。

                  数据规模

                  -1018 vectorlong long st, ed;scanf("%lld%lld", &st, &ed);segs.push_back({ st,ed });}sort(segs.begin(), segs.end());//对区间进行排序，确保第一个区间的左端点是最小的if (segs[0].second