2025 A卷 100分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

2025华为OD真题目录+全流程解析/备考攻略/经验分享

华为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] 即可覆盖整个区间。

---

解题思路

1. 排序线段：将所有线段按起点从小到大排序，若起点相同则按终点从大到小排序。
2. 贪心算法：每次选择能覆盖当前最左端点且右端点最远的线段，逐步扩展覆盖范围。
3. 终止条件：当覆盖范围达到所有线段的最大右端点时结束。

---

代码实现

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);}
}

---

代码详细解析

1. 读取输入

   • 读取线段数量 n，然后逐行读取每个线段的起点和终点，存入 List<Segment>。

2. 排序线段

   • 按起点从小到大排序，若起点相同则按终点从大到小排序。这确保在相同起点的线段中优先选择更长的线段。

3. 确定总区间范围

   • 遍历所有线段，找到最小的起点 L 和最大的终点 R，即所有线段合并后的总区间。

4. 贪心算法核心

   • 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。

---

综合分析

1. 时间复杂度

   • 排序时间复杂度为 O(n log n)。
   • 贪心算法遍历线段时间复杂度为 O(n)。
   • 总体时间复杂度为 O(n log n)，适用于 n ≤ 10000。

2. 空间复杂度

   • 存储线段需要 O(n) 空间。

3. 优势

   • 贪心算法保证每次选择最优线段，确保全局最优。
   • 排序策略简化了后续选择过程。

4. 适用性

   • 适用于需要覆盖连续区间且线段可能重叠的场景。

---

python

问题分析

我们需要从一组线段中选出最少数量的线段，使得它们的并集覆盖所有原始线段的并集。例如，输入三个线段 [1,4]、[2,5]、[3,6]，它们的并集是 [1,6]，选择 [1,4] 和 [3,6] 即可覆盖整个区间。

---

解题思路

1. 排序线段：将线段按起点升序排序，若起点相同则按终点降序排序。
2. 贪心算法：每次选择能覆盖当前最左端点且右端点最远的线段，逐步扩展覆盖范围。
3. 终止条件：当覆盖范围达到所有线段的最大右端点时结束。

---

代码实现

class Segment:def __init__(self, start, end):self.start = startself.end = endn = 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].endi += 1if max_end == -float('inf'):  # 无法覆盖整个区间print(-1)exit