AcWing 907. 区间覆盖
原题链接
简单
作者:
皓首不倦
,
2020-09-05 21:55:12
,
所有人可见
,
阅读 389
'''
贪心策略
所有区间按照起点升序排序,同时维护一个剩余的需要覆盖的区间的左边界,一开始左边界是目标区间的左端点
从左到右枚举所有区间,对于所有左端点小于等于左边界的区间,统计其右端点最大值,如果最大值超过了左边界
就选取这个右端点最大的区间进行覆盖,更新需要覆盖的左边界为选中的区间的右端点,如果中途发现右端点最大
值无法超过或者等于需要覆盖的左边界,则无解,最后覆盖的左边界无法大于等于目标区间的右端点,也无解
统计中途选中的区间的个数即可,这个累加值就是选择区间的最小个数
'''
start, end = map(int, input().split())
n = int(input())
arr = []
for _ in range(n):
a, b = map(int, input().split())
arr.append((a, b))
arr.sort()
left_bound = start
i = 0
fail = False
cnt = 0
while i < len(arr):
max_r = -0x7fffffff
j = i
while j < len(arr):
if arr[j][0] <= left_bound:
max_r = max(max_r, arr[j][1])
else:
break
j += 1
if max_r >= left_bound:
left_bound = max_r
cnt += 1
else:
fail = True
break
if fail:
break
i = j
if max_r >= end:
break
if not fail and left_bound < end:
fail = True
print(-1 if fail else cnt)