zl程序教程

您现在的位置是:首页 >  后端

当前栏目

【华为OD机试真题 java、python、c++】区间交叠问题、最少数量线段覆盖【2022 Q4 200分】

PythonJAVAC++华为 2022 机试 OD 数量
2023-09-11 14:19:50 时间

代码请进行一定修改后使用,本代码保证100%通过率,本题含有java、python、c++三种代码

题目描述

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

输入描述

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

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

输出描述

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

示例1

输入

3
1,4
2,5
3,6

输出

2

题意

给若干个区间,使用其中最少的区间数量,可以覆盖到所有的区间范围

求这个最少的区间数量

比如示例1中选择1,4和3,6就可以覆盖到所有的区间,数量是2个

思路

是贪心实现的,每次找出一个开始点,循环找出这个点前面所有区间的最远尾点,这个最远尾点+1就是下一个开始点。

然后if处理下区间距离不相邻的情