小工具知识网

当前位置: 首页 > 行业知识 > 2024华为OD机试真题【区间交叠/贪心算法】【C++】

行业知识

2024华为OD机试真题【区间交叠/贪心算法】【C++】

2026-11-20 03:03:09 来源:互联网转载

题目描述

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

输入描述

第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”,

x和y 分别表示起点和终点,取值范围是[-10^5 ,10^5]。

输出描述

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

输入

3

1,4

2,5

3,6

输出

2

题意解读

首先,用示例来理解题意:现在有三条线段:

一号线段:起点1,终点4;

二号线段:起点2,终点5;

三号线段:起点3,终点6;

我们要从这三条线段中,选出若干条线段,覆盖1~6整个区间。

比如,我们可以选择 一号、二号、三号。一号覆盖 1~4 ,二号覆盖 2~5,三号覆盖3~6,三条线段加起来可以覆盖1~6整个区间。但是,题目要求尽可能选择少的线段。因此,我们只用选择一号、三号,也能覆盖1~6整个区间。所以,答案就是选择2条线段(即一号、三号)。

解题思路

这是一道典型的贪心算法,贪心策略如下:

首先,将所有线段按起点从小到大排序。

然后遍历排序后的线段,每遍历到一个线段(我们称当前正在遍历的线段为current线段),找出后面的线段中左端点小于等于current线段的右端点的所有线段(我们称之为备选线段),找出备选线段中右端点最大的一个线段maxLine。下一步遍历maxLine。

不断重复以上操作,直到覆盖完整个长度为m的区间,就能得到最少的线段数。

视频讲解

2023华为机试真题【区间交叠/贪心算法】

示例代码(C++)

#include #include #include #include #include using namespace std;// 将字符串形式的线段转换为vectorvector getSegments(const string& line) {    vector segs;    istringstream iss(line);    string x, y;    getline(iss, x, ',');    getline(iss, y);    segs.push_back(atoi(x.c_str()));    segs.push_back(atoi(y.c_str()));    return segs;}// 对线段按照起点进行排序bool compareSegments(const vector& a, const vector& b) {    return a[0] 

上一篇:电脑主机开关线松了怎么办

下一篇:家庭高速服务器怎么选?