모든 집을 데우기 위해 고정된 따뜻한 반경을 가진 표준 히터를 설계해야 한다고 가정합니다. 이제 우리는 수평선에 주택과 히터의 위치를 주었으므로 모든 주택이 히터로 덮일 수 있도록 히터의 최소 반경을 찾아야 합니다. 그래서 주택과 히터를 별도로 제공할 예정이며, 예상 출력은 히터의 최소 반경 기준이 될 것입니다.
따라서 입력이 [1,2,3,4],[1,4]와 같으면 두 히터가 위치 1과 4에 배치되었으므로 출력은 1이 됩니다. 반경 1을 사용해야 하며 모든 집을 따뜻하게 할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
리스트 하우스 정렬
-
목록 히터 정렬
-
res :=집 배열과 같은 크기의 배열이고 inf
를 사용하여 채웁니다. -
범위 0에서 주택 크기까지의 i에 대해
-
h :=주택[i]
-
ind :=목록이 정렬된 상태로 유지되도록 h를 히터에 삽입하는 가장 왼쪽 인덱스
-
ind가 히터의 크기와 같으면
-
res[i] :=최소 res[i], |h - 히터[-1]|
-
-
그렇지 않으면 ind가 0과 같을 때
-
res[i] :=최소 res[i], |h - 히터[0]|
-
-
그렇지 않으면
-
res[i] :=최소 res[i], |h - 히터[ind]| , |h - 히터[ind-1]|
-
-
-
최대 res
반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
bisect import bisect_leftclass 솔루션:def findRadius(self, 집, 히터):house.sort() heaters.sort() res =[float('inf')]*len(houses) for i in range(len (집):h =집[i] ind =bisect_left(히터, h) ind==len(히터)인 경우:res[i] =min(res[i], abs(h - 히터[-1]) ) elif ind ==0:res[i] =min(res[i], abs(h - 히터[0])) else:res[i] =min(res[i], abs(h - 히터[ind]) ]), abs(h - 히터[ind-1])) 반환 max(res)ob =Solution()print(ob.findRadius([1,2,3,4],[1,4])) 입력
[1,2,3,4],[1,4]
출력
1