907. 区间覆盖
摘要
Title: 907. 区间覆盖
Tag: 贪心、最少小区间覆盖大区间
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
907. 区间覆盖
-
题意
给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 −1。 -
思路
用双指针的思想去找，包含st并且右端点最长的区间
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33'''
Author: NEFU AB-IN
Date: 2022-03-15 11:29:16
FilePath: \ACM\Acwing\907.py
LastEditTime: 2022-03-15 11:30:46
'''
st, ed = map(int, input().split())
n = int(input())
a = []
for i in range(n):
l, r = map(int, input().split())
a.append([l, r])
a.sort()
res = 0
for i in range(n):
j = i
r = -int(2e9)
while j < n and a[j][0] <= st:
r = max(r, a[j][1])
j += 1
if r < st: # 如果最右端点连st都到不了，也就是说 右 ~ st 有一段空缺， 说明不符合
res = -1
break
res += 1 # 那么就记上这个区间
if r >= ed: #如果直接大于 ed了，说明区间已经被完全覆盖了
break
i = j - 1 # 因为i会自增，所以要让i下次从j开始，那么就得等于 j-1
st = r # 若等于r + 1，那么（r, r + 1）区间是空的，不符合
print(res)
