- All the houses are left to the first heater. The last house < the first heater:
h1 h2 h3 // houses
* * * // heaters- (Reverse the above case) All the heater are left to the first house. The last heater < the first house:
h1 h2 h3 // heaters
* * * // housesIdea!! To find the minimum required distance to cover all houses, we always find the cloest heater for each house. (Greedy). Then question becomes how to find the closest heater for each house efficiently. For each house, we can find the minimum distance of the previous and next closest heater that can cover it. The answer is the maximum of all minimum distances.
取最小值是因為我們要確保每個房子被最近的加熱器覆蓋，這樣才能保證半徑最小。至於最終答案取最大值，是因為我們要找到覆蓋所有房子的最小半徑，這個半徑必須足夠大以覆蓋最遠的房子。
h1, h2, h3
* | * | * |
|-----^--|------^---|-------^
10 5 15 7 20
distance(h1) = min(10, 5) = 5
distance(h2) = min(15, 7) = 7
distance(h3) = min(20) = 20
ans = 20Pay attention: We should use
heaters[i]andhouses[i]which is the actual position to calculate the distance, not the indexiitself.
We can sort the heaters so that we can use binary search to find the closest heater for each house.
对于每个房屋，要么用前面的暖气，要么用后面的，二者取近的，得到距离。
遍历所有
houses[i]，记录其位置pos，在有序的heaters序列里找到第一个大于（等于）pos的迭代器元素it，判断it和it-1与pos的距离，较小值就是该house[i]的最小供暖半径。
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
* H *
|---3----|--------6---------|
heaterA heaterB- Previous closest heater: Binary search
the last heater <= house[i].
O, O, O, O, X, X, X
^
House- Next closest heater: Binary search
the first heater >= house[i].
X, X, X, X, O, O, O
^
HouseFurthermore, we also have to handle the corner cases (see above):
They are optinal, it can be covered by above bineary search approach.
- The last house < the first heater:
heater[0] - house[i]
h1 h2 // houses
^ ^ |---------|
* * // heaters- The last heater < the first house (reverse the above case):
house[i] - heater[n - 1](nis the size of the heaters array)
h1 h2 // houses
|---------| ^ ^
* * // heatersfun findRadius(houses: IntArray, heaters: IntArray): Int {
heaters.sort()
var minRadius = 0
for (i in 0 until houses.size) {
// (Optional) We can short-circuit the distance calculation if the house
// is on the left of the first heater or on the right of the last heater.
val distance = if (houses[i] <= heaters.first()) {
heaters.first() - houses[i]
} else if (heaters.last <= houses[i]) {
houses[i] - heaters.last()
} else {
// The key part, find the previous and next closest heater for the house.
val previousDistance = searchPreviousHeater(heaters, houses[i])
val nextDistance = searchNextHeater(heaters, houses[i])
minOf(previousDistance, nextDistance)
}
minRadius = maxOf(minRadius, distance)
}
return minRadius
}
// find previous heater, binary search the last heater <= num
// 1, 3, *5 8, 9
// O O O X X
// 6
private fun searchPreviousHeater(heaters: IntArray, house: Int): Int {
var left = 0
var right = heaters.size - 1
while (left <= right) {
val middle = left + (right - left) / 2
if (heaters[middle] > house) {
right = middle - 1
} else if (heaters[middle] < house) {
left = middle + 1
} else {
left = middle + 1
}
}
return if (right in 0 until heaters.size) (house - heaters[right]) else Int.MAX_VALUE
}
// find next heater, binary search the first heater >= num
// 1, 3, 5 *8, 9
// X X X O O
// 6
private fun searchNextHeater(heaters: IntArray, house: Int): Int {
var left = 0
var right = heaters.size - 1
while (left <= right) {
val middle = left + (right - left) / 2
if (heaters[middle] > house) {
right = middle - 1
} else if (heaters[middle] < house) {
left = middle + 1
} else {
right = middle - 1
}
}
return if (left in 0 until heaters.size) (heaters[left] - house) else Int.MAX_VALUE
}- Time Complexity:
O((n * log n + m * log n)wherenis the size of the heaters array andmis the size of the houses array:O(n * log n)for sorting the heaters array.O(m * log n)for binary search the closest heater for each house.
- Space Complexity:
O(log n)for sorting.
fun findRadius(houses: IntArray, heaters: IntArray): Int {
// We should check the heaters size, not houses size, it's used to access the heaters[i] after binary search.
val n = houses.size
heaters.sort()
var radius = 0
for (house in houses) {
// search left closest
val leftIndex = lowerBound(house, heaters)
// search right closest
val rightIndex = upperBound(house, heaters)
// There are two mistakes:
// We don't use the last or first heater if we can't find the left or right closest heater.
// If we use Int.MAX_VALUE, then we should calculate the distance here, not below.
// Correct:
// val left = if (leftIndex in 0 until n) house - heaters[leftIndex] else Int.MAX_VALUE
// val right = if (rightIndex in 0 until n) heaters[rightIndex] - house else Int.MAX_VALUE
// val requiredRadius = minOf(left, right)
val left = if (leftIndex in 0 until n) heaters[leftIndex] else heaters.last()
val right = if (rightIndex in 0 until n) heaters[rightIndex] else heaters.first()
// calculate the minimum of the two distances
val requiredRadius = minOf(house - left, right - house)
// update the global maximum of radius
radius = maxOf(radius, requiredRadius)
}
return radius
}We can also solve this problem using two pointers. The key idea is the same as the binary search approach. We try to locate the next closest heater for each house first, then find the previous closest heater by minus one (if exist or not out of bound) from the next closest heater.
We sort the houses and heaters array first, so that we can iterate each house in order and then find the previous and next closest heater for it.
First we locate the next closest heater of houses[i]:
// Move to the closest next heaters heaters[j] <= houses[i]
houses 7 10
heaters 1 2 5 7
j --------> j'
houses 7 10
heaters 1 2 5 8
j -----------> j'Then the current j and previous position j - 1 of the heater can be the previous and next closest heater for the house. We calculate the minimum distance from the previous and next heaters, and update the answer.
houses h1, h2
i
heaters * * * *
j (next heater)
^
j - 1 (previous heater)Please note that it's necessary to handle the two corner cases explicitly to avoid out of bound when accessing the heaters[j].
fun findRadius(houses: IntArray, heaters: IntArray): Int {
val m = houses.size
val n = heaters.size
houses.sort()
heaters.sort()
var minRadius = 0
var j = 0 // heater index
for (i in 0 until m) {
// We move to the closest "next" heater (e.g. house[i] <= heaters[j]).
while (j < n && heaters[j] < houses[i]) j++
// My mistake: This only locates the last heater that heaters[j] < house[i].
// while (j + 1 < n && heaters[j + 1] <= houses[i]) j++
val distance = if (j == 0) { // Corner case 1: (all houses) ... heaters[0]
heaters.first() - houses[i]
} else if (j == n) { // Corner case 2: (all heaters) ... houses[0]
houses[i] - heaters.last()
} else {
// We do have previous and next heaters.
val previousDistance = houses[i] - heaters[j - 1]
val nextDistance = heaters[j] - houses[i]
minOf(previousDistance, nextDistance)
}
minRadius = maxOf(minRadius, distance)
}
return minRadius
}- Time Complexity:
O(n * log n + m * log m + (m + n))=O(n log n + m * log m)wherenis the size of the heaters array andmis the size of the houses array:O(n * log n)for sorting the heaters array.O(m * log m)for sorting the houses array.
- Space Complexity:
O(log n + log m)for sorting.