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

Every house can be warmed, as long as the house is within the heater's warm radius range.&nbsp;

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters&nbsp;so that those heaters could cover all houses.

Notice that&nbsp;all the heaters follow your radius standard, and the warm radius will the same.

&nbsp;
Example 1:

Input: houses = [1,2,3], heaters = [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: houses = [1,2,3,4], heaters = [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.


Example 3:

Input: houses = [1,5], heaters = [2]
Output: 3


&nbsp;
Constraints:


	1 &lt;= houses.length, heaters.length &lt;= 3 * 104
	1 &lt;= houses[i], heaters[i] &lt;= 109


class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        """

        """

        houses.sort()
        heaters.sort()

        max_radius = -inf

        for house in houses:
            i = bisect_left(heaters, house)

            if i == len(heaters):
                max_radius = max(max_radius, house - heaters[-1])
            elif i == 0:
                max_radius = max(max_radius, heaters[i] - house)
            else:
                curr = heaters[i]
                prev = heaters[i-1]
                max_radius = max(max_radius,min(abs(house - curr), abs(house-prev)))

        return max_radius

    # O(NLOGN)
class Solution {
  public boolean can(int r, int[] houses, int[] heaters) {
    int prevHouseIdx = -1;
    for(int i = 0; i < heaters.length; i++) {
      int from = heaters[i]-r;
      int to   = heaters[i]+r;
      for(int j = prevHouseIdx+1; j < houses.length; j++){
        if(houses[j]<=to && houses[j]>=from){
          prevHouseIdx++;
        }
        else break;
      }
      if(prevHouseIdx >= houses.length-1)return true;
    }
    return prevHouseIdx>= houses.length-1;
  }
  public int findRadius(int[] houses, int[] heaters) {
    Arrays.sort(houses);
    Arrays.sort(heaters);
    int lo = 0, hi = 1000000004;
    int mid, ans = hi;
    while(lo <= hi) {
      mid = (lo+hi)/2;
      if(can(mid, houses, heaters)){
        ans = mid;
        hi = mid - 1;
      } else lo = mid + 1;
    }
    return ans;
  }
}
class Solution {
public:
    //we will assign each house to its closest heater in position(by taking the minimum
    //of the distance between the two closest heaters to the house) and then store the maximum
    //of these differences(since we want to have the same standard radius)
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(heaters.begin(),heaters.end());
        int radius=0;
        for(int house:houses){
            //finding the smallest heater whose position is not greater than
            //the current house
            int index=lower_bound(heaters.begin(),heaters.end(),house)-heaters.begin();
            if(index==heaters.size()){
                index--;
            }
            //the two closest positions to house will be heaters[index] and
            //heaters[index-1]
            int leftDiff=(index-1>=0)?abs(house-heaters[index-1]):INT_MAX;
            int rightDiff=abs(house-heaters[index]);
            radius=max(radius,min(leftDiff,rightDiff));
        }
        return radius;
    }
};
var findRadius = function(houses, heaters) {
	houses.sort((a, b) => a - b);
	heaters.sort((a, b) => a - b);
	let heaterPos = 0;
	const getRadius = (house, pos) => Math.abs(heaters[pos] - house);

	return houses.reduce((radius, house) => {
		while (
			heaterPos < heaters.length &&
			getRadius(house, heaterPos) >= 
			getRadius(house, heaterPos + 1)
		) heaterPos += 1;

		const currentRadius = getRadius(house, heaterPos);
		return Math.max(radius, currentRadius);
	}, 0);
};
Heaters