区间覆盖 python贪心
题目描述
给定 N个闭区间 [ai,bi]以及一个线段区间 [s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。
输出最少区间数,如果无法完全覆盖则输出 −1。
样例
输入
1 5
3
-1 3
2 4
3 5
输出
2
算法1
(贪心) $O(nlogn)$
- 按左端点从小到大对待选区间排序
- 从前往后枚举每个区间,在所有能覆盖start的区间中,选择右端点最大的区间,然后将start更新成右端点最大值
正确性证明思路:假设ans和贪心做法存在不同的区间,则根据贪心策略,可以将此区间替换成贪心所选的区间,因此cnt=ans
python编程注意事项:
1. lambda语法对区间左端点排序
2. 双指针的i循环用while不用range
时间复杂度 $O(nlogn)$
- 排序时间复杂度$O(nlogn)$
- 双指针时间复杂度$O(n)$
Python 代码
st, ed = map(int, input().strip().split())
n = int(input())
my_range = []
for i in range(n):
l, r = map(int, input().strip().split())
my_range.append([l, r])
# 按区间左端点大小排序
my_range.sort(key = lambda x: x[0])
i = 0
res = 0
success = False
# 双指针算法
while i < n:
j, r = i, -2e9
while j < n and my_range[j][0] <= st: # 从所有能覆盖start的区间中,选择右端点最大的
r = max(r, my_range[j][1])
j += 1
if r < st: # 找不到能覆盖start的
res = -1
break
res += 1
if r >= ed: # 成功覆盖目标区间
success = True
break
i = j # 定位到第一个不能覆盖start的区间
st = r # 更新start
if success:
print(res)
else:
print(-1)