forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 65
/
heaters.cpp
23 lines (22 loc) · 845 Bytes
/
heaters.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Time: O((m + n) * logn), m is the number of the houses, n is the number of the heaters.
// Space: O(1)
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(heaters.begin(), heaters.end());
int min_radius = 0;
for (const auto& house : houses) {
auto equal_or_larger = lower_bound(heaters.cbegin(), heaters.cend(), house);
auto curr_radius = numeric_limits<int>::max();
if (equal_or_larger != heaters.cend()) {
curr_radius = *equal_or_larger - house;
}
if (equal_or_larger != heaters.cbegin()) {
auto smaller = prev(equal_or_larger);
curr_radius = min(curr_radius, house - *smaller);
}
min_radius = max(min_radius, curr_radius);
}
return min_radius;
}
};