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