题目描述
给定坐标轴上的一组线段，线段的起点和终点均为整数并且长度不小于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华为机试真题【区间交叠/贪心算法】
示例代码（Python版本）
def main():
# 获取区间个数
count = int(input().strip())
# 排序
intervals = [list(map(int, input().strip().split(','))) for _ in range(count)]
intervals.sort()
interval_stack = [intervals[0]]
# 遍历并合并区间
for i in range(1, len(intervals)):
current_interval = intervals[i]
top_interval = interval_stack[-1] if interval_stack else None
while True:
# 如果栈为空，直接加入当前区间
if not top_interval:
interval_stack.append(current_interval)
break
top_start, top_end = top_interval
current_start, current_end = current_interval
# 当前区间在栈顶区间的左侧且没有重叠
if current_end <= top_start:
break
# 当前区间在栈顶区间的左侧但与其有重叠
elif current_start <= top_start and current_end <= top_end:
break
# 当前区间完全覆盖栈顶区间
elif current_start <= top_start and current_end > top_end:
interval_stack.pop()
# 当前区间在栈顶区间内部，但终点超出
elif current_start > top_start and current_end > top_end:
interval_stack.append([top_end, current_end])
break
# 当前区间在栈顶区间的右侧且没有重叠
else:
interval_stack.append(current_interval)
break
# 更新栈顶区间
top_interval = interval_stack[-1] if interval_stack else None
print(len(interval_stack))
if __name__ == "__main__":
main()
参考文章
发表评论