华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

给定坐标轴O上的一组线段，线段的起点和终点均为整数并且长度不小于1，请你从中找到最少数量的线段，这些线段可以覆盖任所有线段。

二、输入描述

第一行输入为所有线段的数量，不超过10000，后面每行表示一条线段，格式为"x,y"，x和y分别表示起点和终点。

三、输出描述

最少线段数量，为正整数。

四、测试用例

测试用例1：

1、输入

3
1,4
2,5
3,6

2、输出

2

3、说明

选择线段 [1,4] 和 [3,6]，即可覆盖所有线段。

测试用例2：

1、输入

4
1,10
2,3
4,5
6,7

2、输出

1

3、说明

选择线段 [1,10]，即可覆盖所有线段。

五、解题思路

1、贪心算法

贪心算法适用于此类优化问题，通过每次做出局部最优的选择，最终达到全局最优。它在此问题中能够有效地选择最少数量的线段来覆盖所有给定的线段的并集。

排序是贪心算法的前置步骤，通过特定的排序规则（起点升序，终点降序），可以确保在选择线段时，覆盖范围更大的线段优先被选中，从而减少总的选择次数。

数组或列表作为基础的数据结构，方便存储和管理大量的线段，并且能够高效地进行遍历和排序操作。

2、具体步骤

1. 将所有线段按照起点升序排序。如果起点相同，则按照终点降序排序。这有助于在选择线段时，优先考虑起点靠前且覆盖范围更大的线段。
2. 初始化一个变量 currentEnd，用于记录当前已覆盖的最右端点，初始值设为负无穷。
3. 初始化一个变量 count，记录选择的线段数量，初始值为0。
4. 遍历排序后的线段列表，对于每一条线段：
   • 如果当前线段的起点大于 currentEnd，说明现有的覆盖范围无法覆盖这条线段，需要选择一条新的线段来扩展覆盖范围。选择当前线段，并将 currentEnd 更新为该线段的终点，同时将 count 加1。
   • 否则，更新 currentEnd 为当前线段终点与 currentEnd 中的较大值，以扩展覆盖范围。
5. 最终选择的线段数量 count 即为覆盖所有线段所需的最少线段数量。

3、时间复杂度分析

排序步骤的时间复杂度为 O(nlogn)，其中 n 为线段数量。

遍历和选择线段的步骤时间复杂度为 O(n)。

因此，总体时间复杂度为 O(nlogn)，适用于线段数量较大的情况（如本题中的 10000 条线段）。

六、Python算法源码

# 导入必要的模块
import sysdef minimal_cover_segments():# 读取所有输入行lines = sys.stdin.read().strip().split('\n')n = int(lines[0])  # 读取线段数量segments = []# 读取每条线段的起点和终点for i in range(1, n+1):x, y = map(int, lines[i].split(','))if x > y:x, y = y, x  # 确保起点小于等于终点segments.append((x, y))# 按起点升序排序，若起点相同，则按终点降序排序segments.sort(key=lambda s: (s[0], -s[1]))count = 0  # 记录需要的线段数量current_end = -float('inf')  # 当前覆盖的最右端点next_end = -float('inf')  # 在当前覆盖范围内能达到的最远端点i = 0  # 当前遍历到的线段索引while i < n:# 如果当前线段的起点大于当前覆盖范围，需要选择新的线段if segments[i][0] > current_end:# 更新覆盖范围为在当前范围内能达到的最远端点current_end = next_endcount += 1# 如果当前线段的起点仍大于新的覆盖范围，说明无法覆盖if segments[i][0] > current_end:current_end = segments[i][1]count +=1else:# 更新能达到的最远端点next_end = max(next_end, segments[i][1])i +=1# 最后一次更新覆盖范围if next_end > current_end:count +=1# 输出最少线段数量print(count)# 调用主函数
if __name__ == "__main__":minimal_cover_segments()

七、JavaScript算法源码

// 定义主函数
function minimalCoverSegments() {const fs = require('fs');// 读取标准输入const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');const n = parseInt(input[0]); // 读取线段数量let segments = [];// 读取每条线段的起点和终点for (let i = 1; i <= n; i++) {let [x, y] = input[i].split(',').map(Number);if (x > y) {[x, y] = [y, x]; // 确保起点小于等于终点}segments.push([x, y]);}// 按起点升序排序，若起点相同，则按终点降序排序segments.sort((a, b) => {if (a[0] !== b[0]) {return a[0] - b[0];} else {return b[1] - a[1];}});let count = 0; // 记录需要的线段数量let currentEnd = -Infinity; // 当前覆盖的最右端点let nextEnd = -Infinity; // 在当前覆盖范围内能达到的最远端点let i = 0; // 当前遍历到的线段索引while (i < n) {// 如果当前线段的起点大于当前覆盖范围，需要选择新的线段if (segments[i][0] > currentEnd) {// 更新覆盖范围为在当前范围内能达到的最远端点currentEnd = nextEnd;count++;// 如果当前线段的起点仍大于新的覆盖范围，说明无法覆盖if (segments[i][0] > currentEnd) {currentEnd = segments[i][1];count++;}} else {// 更新能达到的最远端点nextEnd = Math.max(nextEnd, segments[i][1]);}i++;}// 最后一次更新覆盖范围if (nextEnd > currentEnd) {count++;}// 输出最少线段数量console.log(count);
}// 调用主函数
minimalCoverSegments();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>// 定义线段结构体
typedef struct {int start;int end;
} Segment;// 比较函数，用于qsort，按起点升序，若起点相同则按终点降序
int compare(const void* a, const void* b) {Segment* s1 = (Segment*)a;Segment* s2 = (Segment*)b;if (s1->start != s2->start) {return s1->start - s2->start;} else {return s2->end - s1->end;}
}int main(){int n;scanf("%d", &n); // 读取线段数量Segment segments[n];// 读取每条线段的起点和终点for(int i=0; i<n; i++) {scanf("%d,%d", &segments[i].start, &segments[i].end);if (segments[i].start > segments[i].end) {// 确保起点小于等于终点int temp = segments[i].start;segments[i].start = segments[i].end;segments[i].end = temp;}}// 按起点升序排序，若起点相同则按终点降序排序qsort(segments, n, sizeof(Segment), compare);int count = 0; // 记录需要的线段数量int currentEnd = -2147483648; // 当前覆盖的最右端点int nextEnd = -2147483648; // 在当前覆盖范围内能达到的最远端点int i =0; // 当前遍历到的线段索引while(i < n){if (segments[i].start > currentEnd){// 更新覆盖范围为在当前范围内能达到的最远端点currentEnd = nextEnd;count++;// 如果当前线段的起点仍大于新的覆盖范围，说明无法覆盖if (segments[i].start > currentEnd){currentEnd = segments[i].end;count++;}} else {// 更新能达到的最远端点if (segments[i].end > nextEnd){nextEnd = segments[i].end;}}i++;}// 最后一次更新覆盖范围if (nextEnd > currentEnd){count++;}// 输出最少线段数量printf("%d\n", count);return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;// 定义线段结构体
struct Segment {int start;int end;
};// 比较函数，用于排序，按起点升序，若起点相同则按终点降序
bool compareSegments(const Segment& a, const Segment& b){if(a.start != b.start){return a.start < b.start;}return a.end > b.end;
}int main(){ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n; // 读取线段数量vector<Segment> segments(n);// 读取每条线段的起点和终点for(int i=0; i<n; i++){char comma;cin >> segments[i].start >> comma >> segments[i].end;if(segments[i].start > segments[i].end){// 确保起点小于等于终点swap(segments[i].start, segments[i].end);}}// 按起点升序排序，若起点相同则按终点降序排序sort(segments.begin(), segments.end(), compareSegments);int count = 0; // 记录需要的线段数量int currentEnd = INT32_MIN; // 当前覆盖的最右端点int nextEnd = INT32_MIN; // 在当前覆盖范围内能达到的最远端点int i =0; // 当前遍历到的线段索引while(i < n){if(segments[i].start > currentEnd){// 更新覆盖范围为在当前范围内能达到的最远端点currentEnd = nextEnd;count++;// 如果当前线段的起点仍大于新的覆盖范围，说明无法覆盖if(segments[i].start > currentEnd){currentEnd = segments[i].end;count++;}} else {// 更新能达到的最远端点if(segments[i].end > nextEnd){nextEnd = segments[i].end;}}i++;}// 最后一次更新覆盖范围if(nextEnd > currentEnd){count++;}// 输出最少线段数量cout << count << "\n";return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。