[LeetCode] 475. Heaters

轉自LeetCode

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.

<Solution>
想法如下

• 先對 houses 和 heaters 做排序

• 計算每個 house 到離他右邊最近的 heater 的距離

• 計算每個 house 到離他左邊最近的 heater 的距離

• 找出每個 house 在前面兩個距離中的最小值。這個就是每個 house 最小需要的 radius

• 然後在所有最小 radius 中，找出最大的，這個就會是最後的答案

code 如下

C++(參考資料)

	class Solution {
	public:
	int findRadius(vector<int>& houses, vector<int>& heaters) {
	sort(houses.begin(), houses.end());
	sort(heaters.begin(), heaters.end());
	const int houseLen = houses.size();
	const int heaterLen = heaters.size();
	vector<int> ans(houseLen, INT_MAX);
	//>> find the distance between house and right nearest heater
	for(int i = 0, h = 0; i < houseLen && h < heaterLen;) {
	if(houses[i] <= heaters[h]) {
	ans[i] = heaters[h] - houses[i];
	++i;
	}
	else {
	++h;
	}
	}
	//>> find the distance between house and left nearest heater
	//>> and compare with the previous ans and then get the min one
	for(int i = houseLen-1, h = heaterLen-1; i >= 0 && h >= 0;) {
	if(houses[i] >= heaters[h]) {
	ans[i] = min(ans[i], houses[i]-heaters[h]);
	--i;
	}
	else {
	--h;
	}
	}
	return *max_element(ans.begin(), ans.end());
	}
	};

view raw heaterRadius.cpp hosted with ❤ by GitHub

Java(參考資料)

Java 有個 Arrays.binarySearch 這個 function可以簡化整體的 code (ref)

	class Solution {
	public int findRadius(int[] houses, int[] heaters) {
	Arrays.sort(heaters);
	int result = Integer.MIN_VALUE;
	int index;
	int leftDist, rightDist;
	for(final int house : houses) {
	index = Arrays.binarySearch(heaters, house);
	if (index < 0) {
	index = -(index+1);
	}
	leftDist = index-1 >= 0 ? house - heaters[index-1] : Integer.MAX_VALUE;
	rightDist = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;
	result = Math.max(result, Math.min(leftDist, rightDist));
	}
	return result;
	}
	}

view raw heaterRadius.java hosted with ❤ by GitHub