475. Heaters

Problem

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:

1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
3. As long as a house is in the heaters' warm radius range, it can be warmed.
4. All the heaters follow your radius standard and the warm radius will the same.

Example 1:

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

Problem Summary

Winter has arrived. Your task is to design a heater with a fixed heating radius to warm all the houses. Now, given the positions of houses and heaters on a horizontal line, find the minimum heating radius that can cover all houses. So, your input will be the positions of the houses and heaters. You will output the minimum heating radius of the heaters.

Explanation:

• The numbers of houses and heaters given are non-negative and will not exceed 25000.
• The positions of houses and heaters given are non-negative and will not exceed 10^9.
• As long as a house is within the radius of a heater (including on the edge), it can be warmed.
• All heaters follow your radius standard, and the heating radius is the same.

Solution Ideas

• Given an array of house coordinates and an array of heater coordinates, representing the coordinates of houses and heaters respectively. The requirement is to find the minimum radius of the heaters so that all houses can receive heat.
• This problem can be solved by brute force. The brute-force solution iterates through the coordinates of each house, then iterates through each heater, finding the heater coordinate closest to the house. Among all these distances, find the maximum value; this maximum distance is the minimum value of the heater radius. Time complexity is O(n^2).
• The optimal solution for this problem is binary search. When finding the heater closest to a house, first sort the heaters, then use binary search to find it. The rest of the approach is the same as the brute-force solution. Time complexity is O(n log n).

Code

package leetcode

import (
	"math"
	"sort"
)

func findRadius(houses []int, heaters []int) int {
	minRad := 0
	sort.Ints(heaters)
	for _, house := range houses {
		// Iterate through house coordinates and maintain the minimum radius of heaters
		heater := findClosestHeater(house, heaters)
		rad := heater - house
		if rad < 0 {
			rad = -rad
		}
		if rad > minRad {
			minRad = rad
		}
	}
	return minRad

}

// Binary search
func findClosestHeater(pos int, heaters []int) int {
	low, high := 0, len(heaters)-1
	if pos < heaters[low] {
		return heaters[low]
	}
	if pos > heaters[high] {
		return heaters[high]
	}
	for low <= high {
		mid := low + (high-low)>>1
		if pos == heaters[mid] {
			return heaters[mid]
		} else if pos < heaters[mid] {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	// Determine which heater on the two sides is closer
	if pos-heaters[high] < heaters[low]-pos {
		return heaters[high]
	}
	return heaters[low]
}

// Solution 2: brute-force search
func findRadius1(houses []int, heaters []int) int {
	res := 0
	for i := 0; i < len(houses); i++ {
		dis := math.MaxInt64
		for j := 0; j < len(heaters); j++ {
			dis = min(dis, abs(houses[i]-heaters[j]))
		}
		res = max(res, dis)
	}
	return res
}