475. Heaters

Link: https://leetcode.com/problems/heaters/

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.

import sys
import bisect

class Solution(object):
    def findRadius(self, houses, heaters):
        """
        :type houses: List[int]
        :type heaters: List[int]
        :rtype: int
        """

        if not houses:
            return 0
        if not heaters:
            return sys.maxint

        max_r = 0

        # sort the heaters
        heaters.sort()

        for house in houses:
            left_index = bisect.bisect_right(heaters, house) - 1
            left_distance = sys.maxint
            if left_index >= 0:
                left_distance = house - heaters[left_index]

            right_index = bisect.bisect_left(heaters, house)
            right_distance = sys.maxint
            if right_index < len(heaters):
                right_distance = heaters[right_index] - house

            max_r = max(max_r, min(left_distance, right_distance))

        return max_r

NOTE

• "bisect.bisect_left" is for seeking the leftmost insert place for the target element.
• "bisect.bisect_right" is for seeking the rightmost insert place for the target element.

FOR EXAMPLE

The given arr is [1, 2, 3], and the target element is 2.

• "bisect.bisect_left(arr, 2)" will return the 1.
• "bisect.bisect_right(arr, 2" will return the 2.

The given arr is [1, 2, 3], and the target element is -1000.

• "bisect.bisect_left(arr, -1000)" will return 0.
• "bisect.bisect_right(arr, -1000)" will return 0.

The given arr is [1, 2, 3], and the target element is 3000.

• "bisect.bisect_left(arr, 3000)" will return 3.
• "bisect.bisect_right(arr, 3000)" will return 3.

Time Limited Exceeded

import sys

class Solution(object):
    def findRadius(self, houses, heaters):
        """
        :type houses: List[int]
        :type heaters: List[int]
        :rtype: int
        """

        if not houses:
            return 0
        if not heaters:
            return sys.maxint

        # sort the heaters
        heaters.sort()

        max_r = 0
        for house in houses:
            max_r = max(max_r, self.get_min_distance_from_nearest_heater(house, heaters))

        return max_r

    def get_min_distance_from_nearest_heater(self, house, heaters):
        # Binary search
        start = 0
        end = len(heaters) - 1
        while start <= end:
            mid = (start + end) / 2
            heater = heaters[mid]
            if heater == house:
                return 0

            if heater > house:
                if mid == 0:
                    return heater - house
                elif mid - 1 >= start and heaters[mid - 1] < house:
                    return min(house - heaters[mid - 1], heaters[mid] - house)

                end -= 1
            else:
                if mid == len(heaters) - 1:
                    return house - heater
                elif mid + 1 <= end and house < heaters[mid + 1]:
                    return min(house - heaters[mid], heaters[mid + 1] - house)

                start += 1

        return -1

Time Limited Exceeded

import sys

class Solution(object):
    def findRadius(self, houses, heaters):
        """
        :type houses: List[int]
        :type heaters: List[int]
        :rtype: int
        """

        if not houses:
            return 0
        if not heaters:
            return sys.maxint

        # sort the heaters
        heaters.sort()

        max_r = 0
        for house in houses:
            left, right = self.binary_search_heater(house, heaters)
            left_distance = sys.maxint
            if left >= 0:
                left_distance = house - heaters[left]

            right_distance = sys.maxint
            if right >= 0:
                right_distance = heaters[right] - house

            max_r = max(max_r, min(left_distance, right_distance))

        return max_r

    def binary_search_heater(self, house, heaters):
        start = 0
        end = len(heaters) - 1
        while start <= end:
            mid = (start + end) / 2
            if house == heaters[mid]:
                return mid, mid

            if house < heaters[mid]:
                if mid - 1 >= start and heaters[mid - 1] < house < heaters[mid]:
                    return mid - 1, mid
                elif mid - 1 < start:
                    return -1, mid

                end -= 1
            else:
                if mid + 1 <= end and heaters[mid] < house < heaters[mid + 1]:
                    return mid, mid + 1
                elif mid + 1 > end:
                    return mid, -1

                start += 1

        return -1, -1