2025 A卷 100分 题型
本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！
华为OD机试真题《最少数量线段覆盖/多线段数据压缩》：
目录
题目名称：最少数量线段覆盖/多线段数据压缩
知识点：排序、贪心算法
时间限制：1秒
空间限制：256MB
限定语言：不限
题目描述
给定坐标轴上的一组线段（起点和终点为整数且长度≥1），从中选出最少数量的线段，使其能覆盖所有线段。
输入描述：
- 第一行为线段数量N（≤10000）
- 后续N行每行为线段起点和终点，格式为"x,y"（取值范围[-10⁵, 10⁵]）
输出描述：
- 最少线段数量（正整数）
示例：
输入：
3
1,4
2,5
3,6
输出：
2
说明：选取线段[1,4]和[3,6]，可覆盖所有线段。
Java
问题分析
我们需要从一组线段中选出最少数量的线段，使得它们的并集覆盖所有原始线段的并集。例如，输入三个线段 [1,4]、[2,5]、[3,6]，它们的并集是 [1,6]，选择 [1,4] 和 [3,6] 即可覆盖整个区间。
解题思路
- 排序线段：将所有线段按起点从小到大排序，若起点相同则按终点从大到小排序。
- 贪心算法：每次选择能覆盖当前最左端点且右端点最远的线段，逐步扩展覆盖范围。
- 终止条件：当覆盖范围达到所有线段的最大右端点时结束。
代码实现
import java.util.*;
class Segment {
int start;
int end;
public Segment(int start, int end) {
this.start = start;
this.end = end;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine(); // 读取换行符
List<Segment> segments = new ArrayList<>();
// 1. 读取所有线段
for (int i = 0; i < n; i++) {
String[] parts = scanner.nextLine().split(",");
int start = Integer.parseInt(parts[0]);
int end = Integer.parseInt(parts[1]);
segments.add(new Segment(start, end));
}
// 2. 排序线段：按起点升序，若起点相同按终点降序
segments.sort((a, b) -> {
if (a.start != b.start) {
return Integer.compare(a.start, b.start);
} else {
return Integer.compare(b.end, a.end);
}
});
// 3. 找到所有线段的合并区间的总范围
int L = Integer.MAX_VALUE;
int R = Integer.MIN_VALUE;
for (Segment seg : segments) {
if (seg.start < L) L = seg.start;
if (seg.end > R) R = seg.end;
}
int count = 0; // 记录选择的线段数量
int currentEnd = L; // 当前覆盖的最右端点
int i = 0; // 遍历线段的指针
// 4. 贪心算法：每次选择能覆盖当前最左端点且最远的线段
while (currentEnd < R) {
int maxEnd = currentEnd; // 当前能覆盖的最远右端点
boolean found = false; // 是否找到可扩展的线段
// 遍历所有起点小于等于 currentEnd 的线段
while (i < segments.size() && segments.get(i).start <= currentEnd) {
if (segments.get(i).end > maxEnd) {
maxEnd = segments.get(i).end;
found = true; // 找到可扩展的线段
}
i++; // 移动指针
}
if (!found) {
// 无解，无法覆盖整个区间
System.out.println(-1);
return;
}
count++; // 选中线段
currentEnd = maxEnd; // 更新当前覆盖的最右端点
}
System.out.println(count);
}
}
代码详细解析
读取输入
- 读取线段数量
n，然后逐行读取每个线段的起点和终点，存入List<Segment>。
- 读取线段数量
排序线段
- 按起点从小到大排序，若起点相同则按终点从大到小排序。这确保在相同起点的线段中优先选择更长的线段。
确定总区间范围
- 遍历所有线段，找到最小的起点
L和最大的终点R，即所有线段合并后的总区间。
- 遍历所有线段，找到最小的起点
贪心算法核心
currentEnd表示当前覆盖的最右端点，初始化为L。- 在每次循环中，找到所有起点小于等于
currentEnd的线段中右端点最大的线段。 - 若找不到能扩展覆盖范围的线段，则输出
-1。 - 每选择一个线段，更新
currentEnd并增加计数器count。
测试示例
示例1：
输入：
3
1,4
2,5
3,6
输出：
2
解析：排序后线段顺序为 [1,4], [2,5], [3,6]。第一次选择 [1,4]，覆盖到4；第二次选择 [3,6]，覆盖到6，总数量为2。
示例2：
输入：
2
1,3
4,6
输出：
-1
解析：线段 [1,3] 和 [4,6] 无法覆盖中间区间 [3,4]，返回 -1。
综合分析
时间复杂度
- 排序时间复杂度为
O(n log n)。 - 贪心算法遍历线段时间复杂度为
O(n)。 - 总体时间复杂度为
O(n log n)，适用于n ≤ 10000。
- 排序时间复杂度为
空间复杂度
- 存储线段需要
O(n)空间。
- 存储线段需要
优势
- 贪心算法保证每次选择最优线段，确保全局最优。
- 排序策略简化了后续选择过程。
适用性
- 适用于需要覆盖连续区间且线段可能重叠的场景。
python
问题分析
我们需要从一组线段中选出最少数量的线段，使得它们的并集覆盖所有原始线段的并集。例如，输入三个线段 [1,4]、[2,5]、[3,6]，它们的并集是 [1,6]，选择 [1,4] 和 [3,6] 即可覆盖整个区间。
解题思路
- 排序线段：将线段按起点升序排序，若起点相同则按终点降序排序。
- 贪心算法：每次选择能覆盖当前最左端点且右端点最远的线段，逐步扩展覆盖范围。
- 终止条件：当覆盖范围达到所有线段的最大右端点时结束。
代码实现
class Segment:
def __init__(self, start, end):
self.start = start
self.end = end
n = int(input())
segments = []
for _ in range(n):
x, y = map(int, input().split(','))
segments.append(Segment(x, y))
# 1. 按起点升序排序，起点相同则按终点降序排序
segments.sort(key=lambda s: (s.start, -s.end))
# 2. 计算总区间的起点L和终点R
if not segments:
print(0)
exit()
L = min(s.start for s in segments)
R = max(s.end for s in segments)
count = 0
current_end = L # 当前覆盖的最右端点
i = 0 # 遍历线段的指针
# 3. 贪心算法：每次选择能覆盖当前最左端点且最远的线段
while current_end < R:
max_end = -float('inf')
# 遍历所有起点 <= current_end 的线段，找到最大终点
while i < len(segments) and segments[i].start <= current_end:
if segments[i].end > max_end:
max_end = segments[i].end
i += 1
if max_end == -float('inf'): # 无法覆盖整个区间
print(-1)
exit