【Day 40 】2024-09-23 - 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.

[Fightforcoding]

def min_radius(nums):
    def can_cover_with_r(r):
        lights_used = 0
        i = 0
        n = len(nums)

        while i < n and lights_used < 3:
            lights_used += 1
            cover_up_to = nums[i] + 2 * r
            while i < n and nums[i] <= cover_up_to:
                i += 1

        return i == n  # Return True if all houses are covered

    nums.sort()
    low, high = 0, (nums[-1] - nums[0]) / 2.0  # The max possible radius is half the range of houses

    while high >=low
        mid = (low + high) / 2.0
        if can_cover_with_r(mid):
            high = mid  
        else:
            low = mid

    return low

Time: O(nlogn)

Space: O(n)

[naomiwufzz]

thoughts

Sort the coordinates. Binary search for r in the range [0,max distance between houses/2]. For each r, try to cover all houses with 3 lights by greedily placing the lights as far to the right as possible while covering the current house.

def can_cover_all_houses(nums, r):
    # We will try to cover all houses with 3 lights and radius r
    lights_used = 0
    i = 0
    n = len(nums)

    while i < n and lights_used < 3:
        # Place the next light to cover house nums[i]
        lights_used += 1
        # Place the light at position nums[i] + r
        light_pos = nums[i] + r
        # Skip all houses covered by this light
        while i < n and nums[i] <= light_pos + r:
            i += 1

    # If all houses are covered
    return i == n

def find_min_radius(nums):
    nums.sort()
    left, right = 0, (nums[-1] - nums[0]) / 2  # Search range for radius

    while right - left > 1e-6:  # Binary search with small tolerance
        mid = (left + right) / 2
        if can_cover_all_houses(nums, mid):
            right = mid  # Try a smaller radius
        else:
            left = mid  # Increase the radius

    return left

time complexity O(nlogn) space complexity O(n)

[qiaoeve]

思路：以三个灯能不能覆盖到所有房子作为逻辑条件，取得最合适的半径r

代码：

def can_cover_with_radius(nums, r):

贪心地用 3 个灯覆盖所有房子

lamps = 3
n = len(nums)
i = 0
while i < n and lamps > 0:
    lamps -= 1  # 放置一个灯
    light_position = nums[i] + r  # 灯放置在 nums[i] + r
    # 跳过所有在 [nums[i], nums[i] + 2*r] 范围内的房子
    while i < n and nums[i] <= light_position + r:
        i += 1
# 如果所有房子都被覆盖，返回 True
return i == n

def min_radius_to_cover(nums): nums.sort() left, right = 0, (nums[-1] - nums[0]) / 2 # 左边界为 0，右边界为最大间距的一半

二分查找最小的 r

while right - left > 1e-6:  # 控制精度在 1e-6
    mid = (left + right) / 2
    if can_cover_with_radius(nums, mid):
        right = mid  # 可以用当前半径覆盖，尝试更小的半径
    else:
        left = mid  # 无法覆盖，尝试更大的半径
return right

时间复杂度：O(nlog(n))

空间复杂度：O(n)