当前位置：首页 > news >正文

华为OD机试 - 区间交叠问题 - 贪心算法（Python/JS/C/C++ 2024 E卷 200分）

news 2025/5/16 17:17:24

在这里插入图片描述

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

专栏导读

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

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

一、题目描述

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

二、输入描述

第一行输入为所有线段的数量，不超过10000，后面每行表示一条线段，格式为“x,y”，x和y分别表示起点和终点，取值范围是[-10⁵, 10⁵]。

三、输出描述

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

四、测试用例

测试用例1：

1、输入

3
1,4
2,5
3,6

2、输出

3、说明

选择线段 [1,4] 和 [3,6]，它们的并集覆盖了所有原始线段的区域 [1,6]。

测试用例2：

1、输入

4
1,2
2,3
3,4
4,5

2、输出

3、说明

需要选择所有线段 [1,2], [2,3], [3,4], [4,5] 来覆盖整个区间 [1,5]。

五、解题思路

题目要求从给定的一组线段中选择最少数量的线段，使得所有给定线段所覆盖的区域（即所有线段的并集）被选出的线段完全覆盖。换句话说，选出的线段的并集应包含所有原始线段的并集。

这是一个典型的区间覆盖问题，可以通过贪心算法高效地解决。

1、具体步骤如下

排序：
- 将所有线段按照起点升序排序。如果起点相同，则按照终点降序排序。
贪心选择：
- 初始化当前覆盖的右端点 currentEnd 为整个覆盖区间的起点（最小起点）。
- 遍历排序后的线段，对于每一步，选择能够覆盖当前未覆盖部分且延伸最远的线段。
- 每选择一条线段，就将 currentEnd 更新为该线段的终点，并增加选择计数。
终止条件：
- 当 currentEnd 达到或超过所有线段的最大终点时，算法结束。

2、时间复杂度

排序的时间复杂度为 O(n log n)，选择过程的时间复杂度为 O(n)，总体时间复杂度为 O(n log n)，适用于线段数量较大的情况（本题中不超过10000条）。

这种方法确保每次选择的线段都能尽可能延伸覆盖范围，从而最小化所需的线段数量。

六、Python算法源码

import sysdef main():import sysimport sys# 读取所有输入input = sys.stdin.read().splitlines()if not input:print(0)returnn = int(input[0])  # 读取线段数量segments = []for i in range(1, n+1):parts = input[i].split(',')start = int(parts[0])end = int(parts[1])if start > end:start, end = end, start  # 确保起点小于等于终点segments.append((start, end))# 按起点升序排序，如果起点相同，按终点降序排序segments.sort(key=lambda x: (x[0], -x[1]))count = 0  # 最少线段数量current_end = -float('inf')  # 当前覆盖的右端点max_end = -float('inf')  # 当前能覆盖到的最大右端点i = 0  # 当前线段索引n = len(segments)while i < n:# 如果当前线段的起点大于当前覆盖的右端点if segments[i][0] > current_end:# 找到所有起点 <= segments[i][0] 的线段中终点最大的max_end = segments[i][1]j = i + 1while j < n and segments[j][0] <= segments[i][0]:if segments[j][1] > max_end:max_end = segments[j][1]j += 1count +=1current_end = max_endi = jelse:# 找到所有起点 <= current_end 的线段中终点最大的max_end = current_endwhile i < n and segments[i][0] <= current_end:if segments[i][1] > max_end:max_end = segments[i][1]i +=1if max_end > current_end:count +=1current_end = max_endelse:i +=1print(count)if __name__ == "__main__":main()

七、JavaScript算法源码

process.stdin.resume();
process.stdin.setEncoding('utf8');let input = '';
process.stdin.on('data', function(chunk) {input += chunk;
});process.stdin.on('end', function() {const lines = input.trim().split('\n');const n = parseInt(lines[0]); // 读取线段数量let segments = [];for (let i = 1; i <= n; i++) {let parts = lines[i].split(',');let start = parseInt(parts[0]);let end = parseInt(parts[1]);if (start > end) { // 确保起点小于等于终点[start, end] = [end, start];}segments.push([start, end]);}// 按起点升序排序，如果起点相同，按终点降序排序segments.sort((a, b) => {if (a[0] !== b[0]) {return a[0] - b[0];} else {return b[1] - a[1];}});let count = 0; // 最少线段数量let current_end = -Infinity; // 当前覆盖的右端点let i = 0;while (i < n) {if (segments[i][0] > current_end) {// 找到所有起点 <= segments[i][0] 的线段中终点最大的let max_end = segments[i][1];let j = i + 1;while (j < n && segments[j][0] <= segments[i][0]) {if (segments[j][1] > max_end) {max_end = segments[j][1];}j++;}count++;current_end = max_end;i = j;} else {// 找到所有起点 <= current_end 的线段中终点最大的let max_end = current_end;while (i < n && segments[i][0] <= current_end) {if (segments[i][1] > max_end) {max_end = segments[i][1];}i++;}if (max_end > current_end) {count++;current_end = max_end;} else {i++;}}}console.log(count);
});

八、C算法源码

#include <stdio.h>
#include <stdlib.h>// 定义线段结构体
typedef struct {int start;int end;
} Segment;// 比较函数，用于qsort排序
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));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 current_end = -2147483648; // 当前覆盖的右端点int i = 0;while (i < n) {if (segments[i].start > current_end) {// 找到所有起点 <= segments[i].start 的线段中终点最大的int max_end = segments[i].end;int j = i + 1;while (j < n && segments[j].start <= segments[i].start) {if (segments[j].end > max_end) {max_end = segments[j].end;}j++;}count++;current_end = max_end;i = j;} else {// 找到所有起点 <= current_end 的线段中终点最大的int max_end = current_end;while (i < n && segments[i].start <= current_end) {if (segments[i].end > max_end) {max_end = segments[i].end;}i++;}if (max_end > current_end) {count++;current_end = max_end;} else {i++;}}}printf("%d\n", count);free(segments);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;elsereturn 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 current_end = INT32_MIN; // 当前覆盖的右端点int i = 0;while(i < n){if(segments[i].start > current_end){// 找到所有起点 <= segments[i].start 的线段中终点最大的int max_end = segments[i].end;int j = i + 1;while(j < n && segments[j].start <= segments[i].start){if(segments[j].end > max_end){max_end = segments[j].end;}j++;}count++;current_end = max_end;i = j;}else{// 找到所有起点 <= current_end 的线段中终点最大的int max_end = current_end;while(i < n && segments[i].start <= current_end){if(segments[i].end > max_end){max_end = segments[i].end;}i++;}if(max_end > current_end){count++;current_end = max_end;}else{i++;}}}cout << count << "\n";return 0;
}