华为OD机试真题—— 最少数量线段覆盖/多线段数据压缩（2025A卷：100分）Java/python/JavaScript/C++/C语言/GO六种最佳实现

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

---

解题思路

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()count += 1current_end = max_end  # 更新当前覆盖的最右端点if current_end >= R:  # 已覆盖整个区间breakprint(count)

---

代码详细解析

1. 读取输入

   n = int(input())
   segments = []
   for _ in range(n):x, y = map(int, input().split(','))segments.append(Segment(x, y))
   

   • 读取线段数量 n，逐行解析线段起点和终点，存入 segments 列表。

2. 排序线段

   segments.sort(key=lambda s: (s.start, -s.end))
   

   • 按起点升序排序，若起点相同则按终点降序排序。确保在相同起点的线段中优先选择更长的线段。

3. 确定总区间范围

   L = min(s.start for s in segments)
   R = max(s.end for s in segments)
   

   • L 是所有线段的最小起点，R 是所有线段的最大终点。

4. 贪心算法核心

   while current_end < R:max_end = -float('inf')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()count += 1current_end = max_end
   

   • current_end 表示当前覆盖的最右端点，初始化为 L。
   • 遍历所有起点小于等于 current_end 的线段，找到其中最大的终点 max_end。
   • 若无法找到（即 max_end 未更新），说明无法覆盖整个区间，输出 -1。
   • 每次选择线段后，更新 current_end 并增加计数器 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)，存储输入的线段信息。
   • 中间变量：O(1)，仅需常数空间。

3. 优势

   • 贪心算法高效：每次选择最优线段，确保全局最优。
   • 排序策略简化逻辑：优先处理起点小且终点大的线段，减少后续遍历次数。

4. 适用场景

   • 需要覆盖连续区间且线段可能重叠的场景。
   • 数据规模较大时仍能保持高效性能。

---

JavaScript

问题分析

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

---

解题思路

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

---

代码实现

const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let n;
let segments = [];
let lineCount = 0;rl.on('line', (line) => {if (lineCount === 0) {n = parseInt(line.trim()); // 读取线段数量lineCount++;} else {// 解析线段起点和终点const [start, end] = line.trim().split(',').map(Number);segments.push({ start, end });lineCount++;if (lineCount === n + 1) {// 所有线段读取完毕，开始处理processSegments();rl.close();}}
});function processSegments() {if (segments.length === 0) {console.log(0);return;}// 1. 排序线段：按起点升序，起点相同则按终点降序segments.sort((a, b) => {if (a.start !== b.start) {return a.start - b.start;} else {return b.end - a.end;}});// 2. 计算总区间的起点L和终点Rlet L = segments[0].start;let R = segments[0].end;for (const seg of segments) {if (seg.start < L) L = seg.start;if (seg.end > R) R = seg.end;}let count = 0; // 记录选择的线段数量let currentEnd = L; // 当前覆盖的最右端点let i = 0; // 遍历线段的指针// 3. 贪心算法：每次选择能覆盖当前最左端点且最远的线段while (currentEnd < R) {let maxEnd = -Infinity;let found = false;// 遍历所有起点 <= currentEnd 的线段，找到最大终点while (i < segments.length && segments[i].start <= currentEnd) {if (segments[i].end > maxEnd) {maxEnd = segments[i].end;found = true;}i++;}// 无法找到可扩展的线段if (!found) {console.log(-1);return;}count++;currentEnd = maxEnd; // 更新当前覆盖的最右端点}console.log(count);
}

---

代码详细解析

1. 读取输入

   • 使用 readline 模块逐行读取输入。
   • 第一行读取线段数量 n，后续行解析为线段对象 { start, end }。

2. 排序线段

   segments.sort((a, b) => {if (a.start !== b.start) return a.start - b.start;else return b.end - a.end;
   });
   

   • 按起点升序排序，若起点相同则按终点降序，确保优先处理更长的线段。

3. 确定总区间范围

   let L = segments[0].start;
   let R = segments[0].end;
   for (const seg of segments) {if (seg.start < L) L = seg.start;if (seg.end > R) R = seg.end;
   }
   

   • 遍历所有线段，找到最小起点 L 和最大终点 R。

4. 贪心算法核心

   while (currentEnd < R) {let maxEnd = -Infinity;let found = false;while (i < segments.length && segments[i].start <= currentEnd) {if (segments[i].end > maxEnd) {maxEnd = segments[i].end;found = true;}i++;}if (!found) {console.log(-1);return;}count++;currentEnd = maxEnd;
   }
   

   • currentEnd 初始化为 L，表示当前覆盖的最右端点。
   • 在每次循环中，找到所有起点小于等于 currentEnd 的线段中的最大终点 maxEnd。
   • 若无法找到（maxEnd 未更新），说明无法覆盖整个区间，输出 -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)，存储输入的线段信息。
   • 中间变量：O(1)，仅需常数空间。

3. 优势

   • 贪心算法高效：每次选择最优线段，确保全局最优。
   • 排序策略简化逻辑：优先处理起点小且终点大的线段，减少后续遍历次数。

4. 适用场景

   • 需要覆盖连续区间且线段可能重叠的场景。
   • 数据规模较大时仍能保持高效性能。

---

C++

问题分析

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

---

解题思路

1. 排序线段：将线段按起点升序排序，若起点相同则按终点降序排序。这确保在相同起点的线段中优先选择更长的线段。
2. 贪心算法：从总覆盖范围的起点开始，每次选择能覆盖当前未被覆盖区域的最长线段，逐步扩展覆盖范围。
3. 终止条件：当覆盖范围达到所有线段的最大右端点时结束。

---

代码实现

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {int n;cin >> n;vector<pair<int, int>> segments;// 读取所有线段for (int i = 0; i < n; ++i) {int x, y;char comma;cin >> x >> comma >> y;segments.emplace_back(x, y);}// 排序线段：起点升序，终点降序sort(segments.begin(), segments.end(), [](const pair<int, int>& a, const pair<int, int>& b) {if (a.first != b.first) {return a.first < b.first;} else {return a.second > b.second;}});if (segments.empty()) {cout << 0 << endl;return 0;}// 计算总区间的起点L和终点Rint L = segments[0].first;int R = segments[0].second;for (const auto& seg : segments) {if (seg.first < L) L = seg.first;if (seg.second > R) R = seg.second;}int current_end = L;  // 当前覆盖的最右端点int max_end = L;      // 当前能覆盖的最远右端点int count = 0;        // 记录选择的线段数量for (const auto& seg : segments) {if (seg.first > current_end) {count++;current_end = max_end;// 如果当前线段的起点仍然超过当前覆盖范围，说明无法覆盖if (seg.first > current_end) {cout << -1 << endl;return 0;}}// 更新最远右端点max_end = max(max_end, seg.second);}// 遍历结束后检查是否覆盖到Rif (current_end < R) {count++;current_end = max_end;if (current_end < R) {cout << -1 << endl;return 0;}}cout << count << endl;return 0;
}

---

代码详细解析

1. 读取输入

   for (int i = 0; i < n; ++i) {int x, y;char comma;cin >> x >> comma >> y;segments.emplace_back(x, y);
   }
   

   • 读取线段数量 n，逐行解析线段的起点和终点，存入 segments 数组。

2. 排序线段

   sort(segments.begin(), segments.end(), [](const pair<int, int>& a, const pair<int, int>& b) {if (a.first != b.first) return a.first < b.first;else return a.second > b.second;
   });
   

   • 按起点升序排序，若起点相同则按终点降序排序。确保优先处理起点小且更长的线段。

3. 确定总区间范围

   int L = segments[0].first;
   int R = segments[0].second;
   for (const auto& seg : segments) {if (seg.first < L) L = seg.first;if (seg.second > R) R = seg.second;
   }
   

   • 遍历所有线段，找到最小起点 L 和最大终点 R，即所有线段的总覆盖范围。

4. 贪心算法核心

   for (const auto& seg : segments) {if (seg.first > current_end) {count++;current_end = max_end;if (seg.first > current_end) {cout << -1 << endl;return 0;}}max_end = max(max_end, seg.second);
   }
   

   • current_end 初始化为 L，表示当前覆盖的最右端点。
   • 遍历线段时，若当前线段的起点超过 current_end，则选中之前的 max_end 对应的线段，并更新 current_end。
   • 若更新后仍无法覆盖当前线段，说明存在间隙，输出 -1。

5. 遍历结束后检查覆盖

   if (current_end < R) {count++;current_end = max_end;if (current_end < R) {cout << -1 << endl;return 0;}
   }
   

   • 确保最终覆盖到总区间的终点 R。若无法覆盖，输出 -1。

---

测试示例

示例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)，存储输入的线段信息。
   • 中间变量：O(1)，仅需常数空间。

3. 优势

   • 贪心高效：每次选择最优线段，确保全局最优。
   • 排序策略：优先处理起点小且更长的线段，减少后续遍历次数。

4. 适用场景

   • 需要覆盖连续区间且线段可能重叠的场景。
   • 数据规模较大时仍能保持高效性能。

---

C语言

问题分析

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

---

解题思路

1. 排序线段：将线段按起点升序排序，若起点相同则按终点降序排序。这确保在相同起点的线段中优先选择更长的线段。
2. 贪心算法：从总覆盖范围的起点开始，每次选择能覆盖当前未被覆盖区域的最长线段，逐步扩展覆盖范围。
3. 终止条件：当覆盖范围达到所有线段的最大右端点时结束。

---

代码实现

#include <stdio.h>
#include <stdlib.h>typedef struct {int start;int end;
} Segment;// 排序函数：起点升序，起点相同则终点降序
int compare(const void *a, const void *b) {Segment *segA = (Segment *)a;Segment *segB = (Segment *)b;if (segA->start != segB->start) {return segA->start - segB->start;} else {return segB->end - segA->end;}
}int main() {int n;scanf("%d", &n);Segment *segments = (Segment *)malloc(n * sizeof(Segment));// 1. 读取输入线段for (int i = 0; i < n; i++) {int x, y;scanf("%d,%d", &x, &y);segments[i].start = x;segments[i].end = y;}// 2. 排序线段qsort(segments, n, sizeof(Segment), compare);if (n == 0) {printf("0\n");free(segments);return 0;}// 3. 计算总区间的起点L和终点Rint L = segments[0].start;int R = segments[0].end;for (int i = 0; i < n; i++) {if (segments[i].start < L) L = segments[i].start;if (segments[i].end > R) R = segments[i].end;}int count = 0;          // 记录选择的线段数量int current_end = L;    // 当前覆盖的最右端点int i = 0;              // 遍历线段的指针// 4. 贪心算法核心while (current_end < R) {int max_end = -1;    // 当前能覆盖的最远右端点int found = 0;       // 是否找到可扩展的线段// 遍历所有起点 <= current_end 的线段，找到最大终点while (i < n && segments[i].start <= current_end) {if (segments[i].end > max_end) {max_end = segments[i].end;found = 1;}i++;}// 无法覆盖整个区间if (!found) {printf("-1\n");free(segments);return 0;}count++;current_end = max_end;  // 更新当前覆盖的最右端点}printf("%d\n", count);free(segments);return 0;
}

---

代码详细解析

1. 读取输入线段

   for (int i = 0; i < n; i++) {int x, y;scanf("%d,%d", &x, &y);segments[i].start = x;segments[i].end = y;
   }
   

   • 使用 scanf 读取线段数量 n 和每个线段的起点和终点，存入动态数组 segments。

2. 排序线段

   qsort(segments, n, sizeof(Segment), compare);
   

   • 按起点升序排序，若起点相同则按终点降序排序。确保优先处理起点小且更长的线段。

3. 确定总区间范围

   int L = segments[0].start;
   int R = segments[0].end;
   for (int i = 0; i < n; i++) {if (segments[i].start < L) L = segments[i].start;if (segments[i].end > R) R = segments[i].end;
   }
   

   • 遍历所有线段，找到最小起点 L 和最大终点 R，即所有线段的总覆盖范围。

4. 贪心算法核心

   while (current_end < R) {int max_end = -1;int found = 0;while (i < n && segments[i].start <= current_end) {if (segments[i].end > max_end) {max_end = segments[i].end;found = 1;}i++;}if (!found) {printf("-1\n");return 0;}count++;current_end = max_end;
   }
   

   • current_end 初始化为 L，表示当前覆盖的最右端点。
   • 遍历所有起点小于等于 current_end 的线段，找到其中的最大终点 max_end。
   • 若找不到（即 max_end 未更新），说明存在间隙无法覆盖，输出 -1。
   • 每选择一条线段，更新 current_end 并增加计数器 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)，存储输入的线段信息。
   • 中间变量：O(1)，仅需常数空间。

3. 优势

   • 贪心高效：每次选择最优线段，确保全局最优。
   • 排序策略：优先处理起点小且更长的线段，减少后续遍历次数。

4. 适用场景

   • 需要覆盖连续区间且线段可能重叠的场景。
   • 数据规模较大时仍能保持高效性能。

---

GO

问题分析

给定多个线段，要求选择最少数量的线段，使得它们的并集覆盖所有原始线段的并集。例如，输入三个线段 [1,4]、[2,5]、[3,6]，它们的并集是 [1,6]，选择 [1,4] 和 [3,6] 即可覆盖整个区间。若无法覆盖所有原始线段的并集，返回 -1。

---

解题思路

1. 排序线段：按起点升序排序，若起点相同则按终点降序排序。确保优先处理起点小且更长的线段。
2. 确定总覆盖范围：找到所有线段的最小起点 L 和最大终点 R。
3. 贪心算法：从 L 开始，每次选择能覆盖当前未被覆盖区域的最长线段，逐步扩展覆盖范围，直到覆盖 R。
4. 终止条件：若无法扩展覆盖范围，说明存在间隙，返回 -1。

---

代码实现

package mainimport ("bufio""fmt""os""sort""strconv""strings"
)type Segment struct {Start intEnd   int
}func main() {scanner := bufio.NewScanner(os.Stdin)scanner.Scan() // 读取线段数量n, _ := strconv.Atoi(scanner.Text())segments := make([]Segment, n)for i := 0; i < n; i++ {scanner.Scan()line := scanner.Text()parts := strings.Split(line, ",")start, _ := strconv.Atoi(parts[0])end, _ := strconv.Atoi(parts[1])segments[i] = Segment{Start: start, End: end}}// 1. 排序线段：起点升序，起点相同则终点降序sort.Slice(segments, func(i, j int) bool {if segments[i].Start != segments[j].Start {return segments[i].Start < segments[j].Start}return segments[i].End > segments[j].End})if len(segments) == 0 {fmt.Println(0)return}// 2. 计算总区间的起点L和终点RL := segments[0].StartR := segments[0].Endfor _, seg := range segments {if seg.Start < L {L = seg.Start}if seg.End > R {R = seg.End}}count := 0          // 记录选择的线段数量currentEnd := L     // 当前覆盖的最右端点index := 0          // 遍历线段的指针maxEnd := -1 << 31  // 当前能覆盖的最远右端点// 3. 贪心算法核心for currentEnd < R {// 找到所有起点 <= currentEnd 的线段中的最大终点maxEnd = -1 << 31found := falsefor index < len(segments) && segments[index].Start <= currentEnd {if segments[index].End > maxEnd {maxEnd = segments[index].Endfound = true}index++}if !found { // 无法扩展覆盖范围fmt.Println(-1)return}count++             // 选中线段currentEnd = maxEnd // 更新当前覆盖的最右端点}fmt.Println(count)
}

---

代码详细解析

1. 读取输入

   scanner := bufio.NewScanner(os.Stdin)
   scanner.Scan()
   n, _ := strconv.Atoi(scanner.Text())
   

   • 使用 bufio.Scanner 读取输入，第一行为线段数量 n。

2. 解析线段

   for i := 0; i < n; i++ {scanner.Scan()line := scanner.Text()parts := strings.Split(line, ",")start, _ := strconv.Atoi(parts[0])end, _ := strconv.Atoi(parts[1])segments[i] = Segment{Start: start, End: end}
   }
   

   • 逐行读取线段数据，解析为 Segment 结构体。

3. 排序线段

   sort.Slice(segments, func(i, j int) bool {if segments[i].Start != segments[j].Start {return segments[i].Start < segments[j].Start}return segments[i].End > segments[j].End
   })
   

   • 按起点升序排序，若起点相同则按终点降序排序，优先处理更长的线段。

4. 确定总覆盖范围

   L := segments[0].Start
   R := segments[0].End
   for _, seg := range segments {if seg.Start < L {L = seg.Start}if seg.End > R {R = seg.End}
   }
   

   • 遍历所有线段，找到最小起点 L 和最大终点 R。

5. 贪心算法核心

   for currentEnd < R {maxEnd = -1 << 31found := falsefor index < len(segments) && segments[index].Start <= currentEnd {if segments[index].End > maxEnd {maxEnd = segments[index].Endfound = true}index++}if !found {fmt.Println(-1)return}count++currentEnd = maxEnd
   }
   

   • 从 L 开始，每次找到能覆盖当前未被覆盖区域的最长线段，更新 currentEnd 并计数。
   • 若无法找到可扩展的线段，说明存在间隙，返回 -1。

---

测试示例

示例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] 无法覆盖中间间隙，输出 -1。

---

综合分析

1. 时间复杂度

   • 排序：O(n log n)，排序线段的时间复杂度。
   • 贪心遍历：O(n)，每个线段最多被遍历一次。
   • 总复杂度：O(n log n)，适合处理 n ≤ 10000 的数据规模。

2. 空间复杂度

   • 存储线段：O(n)，存储输入的线段信息。
   • 中间变量：O(1)，仅需常数空间。

3. 优势

   • 贪心高效：每次选择最优线段，确保全局最优。
   • 排序策略：优先处理起点小且更长的线段，减少后续遍历次数。

4. 适用场景

   • 需要覆盖连续区间且线段可能重叠的场景。
   • 数据规模较大时仍能保持高效性能。

---

更多内容：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！