2022-01-27: heater. Winter has come. Your task is to design a

2022-01-27： heater .

Winter has come . Your task is to design a heater with fixed heating radius to heat all houses .

Every house within the heating radius of the heater can be heated .

Now? , Give the house on a horizontal line houses And heater heaters The location of , Please find and return the minimum heating radius that can cover all houses .

explain ： All heaters follow your radius standard , The radius of the heating is the same .

Input : houses = 1,2,3,4, heaters = 1,4

Output : 1

explain : In position 1, 4 There are two heaters on it . We need to set the heating radius to 1, So that all the houses can be heated .

Power button 475.

answer 2022-01-27：

Sort houses and heaters .

For example, the place is 7, 9, 14

The location of the heating point : 1 3 4 5 13 15 17

Look at the location first 7

from 1 Heating , Radius is 6

from 3 Heating , Radius is 4

from 4 Heating , Radius is 3

from 5 Heating , Radius is 2

from 13 Heating , Radius is 6

Thus we can see that , place 7 It should be heated by the heating point 5 To heat , Radius is 2

Look at the location 9

The heating point does not go back

from 5 Heating , Radius is 4

from 13 Heating , Radius is 4

from 15 Heating , Radius is 6

Thus we can see that , place 9 It should be heated by the heating point 13 To heat , Radius is 4

Why 13 instead of 5？ Because the next places will be closer to the right , So when the radius is the same , You should choose a more right heating point

Look at the location 14

The heating point does not go back

from 13 Heating , Radius is 1

from 15 Heating , Radius is 1

from 17 Heating , Radius is 3

Thus we can see that , place 14 It should be heated by the heating point 15 To heat , Radius is 1

And so on

Time complexity ：O(N).

Extra space complexity ：O(1).

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
    "sort"
)

func main() {
    houses := []int{1, 2, 3, 4}
    heaters := []int{1, 4}
    ret := findRadius(houses, heaters)
    fmt.Println(ret)
}
func findRadius(houses []int, heaters []int) int {
    sort.Ints(houses)
    sort.Ints(heaters)
    ans := 0
    //  Time complexity O(N)
    // i It's the place ,j It's a heating point 
    for i, j := 0, 0; i < len(houses); i++ {
        for !best(houses, heaters, i, j) {
            j++
        }
        ans = getMax(ans, abs(heaters[j]-houses[i]))
    }
    return ans
}

//  This function means ：
//  Current location houses[i] from heaters[j] Is it the best way to heat ？
//  Current location houses[i] from heaters[j] To heat , The resulting radius is a
//  Current location houses[i] from heaters[j + 1] To heat , The resulting radius is b
//  If a < b,  Description is optimal , Heating should not jump to the next position 
//  If a >= b,  Description is not optimal , Should jump to the next position 
func best(houses, heaters []int, i, j int) bool {
    return j == len(heaters)-1 || abs(heaters[j]-houses[i]) < abs(heaters[j+1]-houses[i])
}

func abs(a int) int {
    if a < 0 {
        return -a
    } else {
        return a
    }
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

The results are as follows ：

picture

---

Zuo Shen java Code