간격 목록이 있다고 가정합니다. 여기서 간격[i]에는 한 쌍(left_i, right_i)이 왼쪽_i에서 시작하여 right_i(둘 다 포함)에서 끝나는 i번째 간격을 나타냅니다. 또한 쿼리라는 또 다른 배열이 있습니다. j번째 쿼리에 대한 답은 left_i <=쿼리[j] <=right_i가 되도록 가장 작은 간격 i의 크기입니다. 그러한 간격을 찾을 수 없으면 -1을 반환합니다. 쿼리에 대한 답변이 포함된 배열을 찾아야 합니다.
따라서 입력이 간격 =[[2,5],[3,5],[4,7],[5,5]] 쿼리 =[3,4,5,6]인 경우 출력은 쿼리는 다음과 같이 처리되기 때문에 [3, 3, 1, 4]입니다 -
-
for query =3:간격 [3,5]는 3을 포함하는 가장 작은 간격입니다. 따라서 5 - 3 + 1 =3입니다.
-
for query =4:간격 [3,5]는 4를 포함하는 가장 작은 간격입니다. 따라서 5 - 3 + 1 =3입니다.
-
for query =5:간격 [5,5]는 5를 포함하는 가장 작은 간격입니다. 따라서 5 - 5 + 1 =1입니다.
-
쿼리 =6의 경우:간격 [4,7]은 6을 포함하는 가장 작은 것이므로 7 - 4 + 1 =4입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
간격 :=목록 간격을 역순으로 정렬
-
h :=새 목록
-
res :=새 지도
-
정렬된 쿼리 목록의 각 q에 대해 수행
-
간격이 비어 있지 않고 마지막 간격의 종료 시간 <=q, do
-
(i, j) :=간격에서 마지막 간격, 제거
-
j>=q이면
-
힙에 쌍(j-i+1, j) 삽입 h
-
-
-
h는 비어 있지 않고 h
-
h에서 맨 위 요소 삭제
-
-
res[q] :=h가 비어 있지 않으면 h의 최상위 간격 시작 시간, 그렇지 않으면 -1
-
-
쿼리의 모든 q에 대해 res[q] 목록을 반환합니다.
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
import heapq
def solve(intervals, queries):
intervals = sorted(intervals)[::-1]
h = []
res = {}
for q in sorted(queries):
while intervals and intervals[-1][0] <= q:
i, j = intervals.pop()
if j >= q:
heapq.heappush(h, [j - i + 1, j])
while h and h[0][1] < q:
heapq.heappop(h)
res[q] = h[0][0] if h else -1
return [res[q] for q in queries]
intervals = [[2,5],[3,5],[4,7],[5,5]]
queries = [3,4,5,6]
print(solve(intervals, queries)) 입력
[[2,5],[3,5],[4,7],[5,5]], [3,4,5,6]
출력
[3, 3, 1, 4]