2026 华为OD机试真题 9月2日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

在一根很高的竹子上生活着一群螳螂，每只螳螂都有一段自己的势力范围，不同螳螂在竹子上的领地有可能重叠，当发现自己的领地内出现其它螳螂时就会战斗，失败一方领地会被胜利一方螳螂占领。

2026 华为OD机试真题 9月2日华为OD上机新系统考试真题 100 分题型

输入描述

给定一个螳螂领地信息 originalLand[i] 数组：originalLand[i] = [x, y] 表示第 i 只螳螂的领地在离地高度 [x,y] 之间的主干上 (x\<y)。螳螂的数量在 [1,50] 之间，螳螂领地坐标 [x,y] 中，0≤x\<y≤150。

输出描述

请返回领地斗争结束后螳螂们的领地信息。返回的领地信息数组中，按照领地坐标升序返回；正确示例：[[3,7],[9,13]]，错误示例：[[9,13],[3,7]]。

示例1

输入

[[1,5],[4,6],[8,15]]

输出

[[1,6],[8,15]]

说明

第一只螳螂的领地范围 [1,5] 和第二只螳螂的领地范围 [4,6] 有重叠，因此两只螳螂在巡逻过程中会发生冲突，最终一只螳螂被打败，两只螳螂的领地被胜利者占有，领地范围变为 [1,6]。

示例2

输入

[[3,7],[9,13]]

输出

[[3,7],[9,13]]

说明

两只螳螂的领地范围没有重叠，因此不会发生冲突，所以最终的领地状态和最初的领地状态是一致的。

示例3

输入

[[1,4],[4,5]]

输出

[[1,5]]

说明

两只螳螂领地边界接触时也会触发冲突，形成领地合并。

解题思路

核心思想

把每只螳螂的领地看成一个闭区间。将所有区间按左端点升序排序后，从左到右线性扫描：

• 如果当前区间的左端点大于已合并区间的右端点，说明没有冲突，直接开启新区间；
• 否则说明存在重叠或端点接触，需要合并，把右端点更新为两者右端点的最大值。

算法步骤

1. 将输入区间转成二维数组并按左端点、右端点排序。
2. 取第一个区间作为当前合并段。
3. 依次扫描后续区间：
   • 若 x > last_end，加入一个新段；
   • 否则更新当前段的右端点 last_end = max(last_end, y)。
4. 输出合并后的所有区间。

复杂度分析

设区间数量为 n。

• 时间复杂度：O(n log n)，来自排序。
• 空间复杂度：O(n)，用于存储区间