【Day 40 】2024-05-17 - 796. Minimum Light Radius

[azl397985856]

796. Minimum Light Radius

入选理由

暂无

题目地址

https://binarysearch.com/problems/Minimum-Light-Radius

前置知识

• 排序
• 二分法

  题目描述

  
  You are given a list of integers nums representing coordinates of houses on a 1-dimensional line. You have 3 street lights that you can put anywhere on the coordinate line and a light at coordinate x lights up houses in [x - r, x + r], inclusive. Return the smallest r required such that we can place the 3 lights and all the houses are lit up.

Constraints

n ≤ 100,000 where n is the length of nums Example 1 Input nums = [3, 4, 5, 6] Output 0.5 Explanation If we place the lamps on 3.5, 4.5 and 5.5 then with r = 0.5 we can light up all 4 houses.

[Martina001]

这个题号在力扣里好像不是本题

[maike-hps]

def minRadius(nums): nums.sort() n = len(nums) left, right = 0, nums[-1] - nums[0]

while left <= right:
    mid = (left + right) / 2
    if canLightAllHouses(nums, n, mid):
        right = mid - 1
    else:
        left = mid + 1

return left

def canLightAllHouses(nums, n, r): count = 1 # 初始时，第一个灯已经放置 i = 0 # 当前房子的索引 for j in range(1, n):

如果当前房子不能被照亮，则需要放置新的灯

    if nums[j] - nums[i] > 2 * r:
        # 尝试找到下一个灯的位置
        while nums[j] - nums[i] > 2 * r:
            i += 1
        count += 1  # 放置了新的灯
        # 如果已经放置了3个灯，则所有房子都能被照亮
        if count == 3:
            return True
return count == 3

[xil324]

class Solution(object):
    def findRadius(self, houses, heaters):
        """
        :type houses: List[int]
        :type heaters: List[int]
        :rtype: int
        """
        heaters.sort()
        houses.sort()
        left = 0
        right = int(1e9)
        while left < right:
            mid = (left + right) // 2
            if self.isFeasible(heaters,houses,mid):
                right = mid
            else:
                left = mid + 1
        return left

    def isFeasible(self, heaters, houses,radius):
        house_index = 0
        heater_index = 0
        while house_index < len(houses):
            if heater_index >= len(heaters):
                return False
            left_cover_range = heaters[heater_index] - radius
            right_cover_range = heaters[heater_index] + radius
            if houses[house_index] < left_cover_range:
                return False
            if houses[house_index] > right_cover_range:
                heater_index += 1
            else:
                house_index += 1
        return True

[Hermione666]

class Solution: def solve(self, nums): nums.sort() N = len(nums) if N <= 3: return 0 LIGHTS = 3

    def possible(diameter):
        start = nums[0]
        end = start + diameter
        for i in range(LIGHTS):
            idx = bisect_right(nums, end)
            if idx >= N:
                return True
            start = nums[idx]
            end = start + diameter
        return False

    l, r = 0, nums[-1] - nums[0]
    while l <= r:
        mid = (l + r) // 2
        if possible(mid):
            r = mid - 1
        else:
            l = mid + 1
    return l / 2

[Dtjk]

class Solution { public: int findRadius(vector& houses, vector& heaters) { sort(houses.begin(),houses.end()); sort(heaters.begin(),heaters.end()); int ans = 0; int h = 0; for(int i=0;i<houses.size();i++){ while(h+1<heaters.size() && abs(houses[i]-heaters[h])>=abs(houses[i]-heaters[h+1])) h++; ans = max(ans,abs(houses[i]-heaters[h])); } return ans; } };