Giả sử ta phải thiết kế một bộ sưởi tiêu chuẩn với bán kính sưởi cố định để sưởi ấm tất cả các ngôi nhà. Bây giờ, ta có vị trí của các ngôi nhà và bộ sưởi trên một đường thẳng ngang, ta cần tìm bán kính tối thiểu của bộ sưởi sao cho tất cả các ngôi nhà có thể được bao phủ bởi các bộ sưởi đó. Vì vậy, ta sẽ cung cấp danh sách nhà và bộ sưởi riêng biệt, và đầu ra mong đợi sẽ là bán kính tiêu chuẩn tối thiểu của bộ sưởi.
Ví dụ, nếu đầu vào là [1,2,3,4],[1,4], thì đầu ra sẽ là 1 vì hai bộ sưởi đặt tại vị trí 1 và 4. Ta phải dùng bán kính 1, thì tất cả các ngôi nhà đều được sưởi ấm.
Để giải quyết, ta thực hiện các bước sau:
- Sắp xếp danh sách houses
- Sắp xếp danh sách heaters
- res := mảng kích thước bằng mảng houses, điền bằng inf
- Với i từ 0 đến kích thước houses, thực hiện:
- h := houses[i]
- ind := chỉ số chèn trái nhất để chèn h vào heaters sao cho danh sách vẫn sắp xếp
- Nếu ind bằng kích thước heaters, thì
- res[i] := min của res[i], |h - heaters[-1]|
- Ngược lại, nếu ind bằng 0, thì
- res[i] := min của res[i], |h - heaters[0]|
- Ngược lại,
- res[i] := min của res[i], |h - heaters[ind]|, |h - heaters[ind-1]|
- Trả về max của res
Ví dụ
Hãy xem triển khai sau để hiểu rõ hơn:
from bisect import bisect_left class Solution: def findRadius(self, houses, heaters): houses.sort() heaters.sort() res = [float('inf')]*len(houses) for i in range(len(houses)): h = houses[i] ind = bisect_left(heaters, h) if ind == len(heaters): res[i] = min(res[i], abs(h - heaters[-1])) elif ind == 0: res[i] = min(res[i], abs(h - heaters[0])) else: res[i] = min(res[i], abs(h - heaters[ind]), abs(h - heaters[ind-1])) return max(res) ob = Solution() print(ob.findRadius([1,2,3,4],[1,4]))Đầu vào
[1,2,3,4],[1,4]
Đầu ra
1