room이라는 배열이 있다고 가정합니다. 여기서 rooms[i]에는 [roomId_i, size_i] 쌍이 포함되며 id가 roomId_i이고 size가 size_i인 방을 나타냅니다. 모든 객실 번호가 다릅니다. 또한 query[j]에 [preferred_j, minSize_j] 쌍이 포함된 또 다른 배열 쿼리가 있습니다. j 번째 쿼리에 대한 대답은 다음과 같은 방의 방 번호 id입니다. -
-
방의 크기는 최소 minSize_j이고
-
|id - 선호하는_j| 최소화됩니다.
이제 절대차이가 동률이면 id가 가장 작은 방을 사용합니다. 그런 공간이 없으면 -1을 반환합니다. 그래서 우리는 j번째 질의에 대한 답변을 담고 있는 질의와 길이가 같은 answer라는 배열을 찾아야 합니다.
따라서 입력이 방 =[[2,2],[1,2],[3,2]] 쿼리 =[[3,1],[3,3],[5,2]]인 경우
때문에 출력은 [3, -1, 3]이 됩니다.-
쿼리 [3,1]의 경우:|3 - 3| 때문에 방 3이 가장 가깝습니다. =0이고 2의 크기는 1 이상이므로 답은 3입니다.
-
쿼리 [3,3]의 경우:크기가 3 이상인 방이 없으므로 답은 -1입니다.
-
쿼리 [5,2]의 경우:|3 - 5| 때문에 방 3이 가장 가깝습니다. =2이고 2의 크기는 2 이상이므로 답은 3입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
크기를 기준으로 방을 정렬하고 크기가 같으면 방 ID를 기준으로 합니다.
-
쿼리 =인덱스 i에 대한 쌍(qid,size,i) 및 쿼리의 쌍(qid, 크기) 목록
-
크기를 기준으로 역순으로 쿼리를 정렬하고 크기가 같으면 선호하는 기준으로, 둘 다 같으면 인덱스 기준으로 정렬
-
ans :=쿼리의 크기와 같은 크기의 배열이고 -1로 채움
-
X :=새 목록
-
쿼리의 각 (qid, size, i)에 대해 수행
-
동안 방 및 방의 마지막 항목 크기>=크기, 수행
-
(idr, p) :=방에서 마지막 요소 삭제
-
idr 삽입 후 X 정렬
-
-
X가 비어 있지 않으면
-
j :=X 정렬 상태를 유지하기 위해 qid를 삽입할 인덱스
-
j가 X의 크기와 같으면
-
ans[i] :=X의 마지막 요소
-
-
그렇지 않으면 j가 0과 같을 때
-
ans[i] :=X[0]
-
-
그렇지 않으면
-
X[j] - qid
-
ans[i] :=X[j]
-
-
그렇지 않으면
-
ans[i] :=X[j-1]
-
-
-
-
-
반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다.
import bisect
def solve(rooms, queries):
rooms.sort(key = lambda x: (x[1], x[0]))
queries = [(qid,size,i) for i, (qid, size) in enumerate(queries)]
queries.sort(key = lambda x: (x[1], x[0], x[2]), reverse = True)
ans = [-1] * len(queries)
X = []
for qid, size, i in queries:
while rooms and rooms[-1][1] >= size:
idr, _ = rooms.pop()
bisect.insort(X, idr)
if X:
j = bisect.bisect(X, qid)
if j == len(X):
ans[i] = X[-1]
elif j == 0:
ans[i] = X[0]
else:
if X[j] - qid < qid - X[j-1]:
ans[i] = X[j]
else:
ans[i] = X[j-1]
return ans
rooms = [[2,2],[1,2],[3,2]]
queries = [[3,1],[3,3],[5,2]]
print(solve(rooms, queries)) 입력
[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]
출력
[3, -1, 3]