6.28华为OD机试真题 新系统 - 统计不重叠区间的个数 (JavaPyCC++JsGo)

统计不重叠区间的个数

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

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

题目描述

给定一个以二维数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i]=[starti,endi]（starti 和 endi 都是整数），这些区间之间可能存在重叠，请统计跟其他任何区间都不重叠的区间数量。

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

输入描述

一个二维数组 intervals，intervals[i] 表示第 i 个区间，intervals[i][0] 表示第 i 个区间的 starti，intervals[i][1] 表示第 i 个区间的 endi。

格式：[[start1,end1],[start2,end2],...]

输出描述

这个区间集合中跟其他区间都不重叠的区间数量。

补充说明

1. 1≤intervals.length≤10000
2. intervals[i].length==2
3. 0≤starti≤endi≤10000

示例1

输入

[[8,10],[1,4],[2,6],[15,18]]

输出

2

说明

区间 [8,10] 和 [15,18] 跟其他区间都不重合

示例2

输入

[[2,4],[4,6]]

输出

0

说明

[2,4] 和 [4,6] 这 2 个区间重叠，不存在跟其他区间都不重叠的区间，故返回 0

解题思路

核心思想

穷举检测：对于每个区间，检查它是否与任何其他区间重叠。

关键观察： - 区间 [s1, e1] 和 [s2, e2] 重叠的判定条件：s1 <= e2 and s2 <= e1- 如果一个区间与所有其他区间都不重叠，则它是"孤立"的

算法策略： - 遍历每个区间 - 对当前区间，检查它是否与任何其他区间相交 - 如果都不相交，则计数器 +1

算法步骤

1. 读取区间数组
2. 对每个区间 i： - 设置isolated = True- 遍历其他区间 j（j ≠ i） - 如果区间 i 和 j 重叠，设置isolated = False并 break - 如果isolated仍为 True，计数器 +1
3. 返回计数器

复杂度分析

• 时间复杂度：O(n²)，需要两两比较
• 空间复杂度