leetcode-475-供暖器

供暖器

题面

leetcode题目

冬季已经来临。你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋\(houses\)和供暖器\(heaters\)的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

example

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

数据范围

• \(1 \leq houses.length, heaters.length \leq 3 \times 10^4\)
• \(1 \leq houses[i], heaters[i] \leq 10^9\)

题解

总体思路

比较明显的一道二分答案查找,我们考虑二分答案范围为\(10^9\),对于每次查找，我们可以通过一个\(O(houses.length \times heaters.length)\)的算法来判断答案是否满足条件，这是显然的，那么我们算一下复杂度为: \[O(\ln{10^9} \times houses.length \times heaters.length) = O(9\ln10 \times houses.length \times heaters.length)\] 代入数据范围发现已经达到了\(O(6\times 10^9)\)大约这个范围，已经有点超出时间限制了，需要继续考虑优化。 我们再来看判断是否满足条件这部分，对于每个房屋\(houses[i]\)我们实际上只需要在\(heaters\)中查找是否满足一个值\(j\)，使得\(heaters[j]\)这个供暖期刚好能覆盖当前房屋即可。假如\(heaters\)是有序数组的话，这个步骤可以通过二分查找来实现，这样这一部分的复杂度就优化为了\(O(houses.length \times \ln {heaters.length})\)，考虑到对于数组排序只需要进行一次，那么最终的复杂度为 \[O(heaters.length \times \ln{heaters.length} + \ln{10^9} \times houses.length \times \ln{heaters.length})\] 这个时候就已经满足条件了，所以这实际上是一个二分套二分的解法。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
#define _DEBUG

#define INF 0x7f7f7f7f
// submit
struct cmp
{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        if (a.first < b.first)
        {
            return true;
        }
        if (a.first == b.first && a.second < b.second)
        {
            return true;
        }
        return false;
    }
};

class Solution
{
public:
    int minVal;
    bool findInVec(int left, int right, int targetVal, int radius, vector<int> &data)
    {
        if (left > right)
        {
            return false;
        }
        int mid = (left + right) / 2;
        int midVal = data[mid];
        if (midVal - radius <= targetVal && targetVal <= midVal + radius)
        {
            return true;
        }
        if (targetVal > midVal + radius)
        {
            return findInVec(mid + 1, right, targetVal, radius, data);
        }
        return findInVec(left, mid - 1, targetVal, radius, data);
    }

    void find(int left, int right, vector<int> &houses, vector<int> &heaters)
    {
        if (left > right)
        {
            return;
        }

        int mid = (left + right) / 2;
        bool allMatch = true;
        int heatersNum = heaters.size();
        for (int i = 0; i < houses.size(); i++)
        {
            int house = houses[i];
            bool find = findInVec(0, heatersNum - 1, house, mid, heaters);
            if (!find)
            {
                allMatch = false;
                break;
            }
        }
        if (allMatch)
        {
            minVal = mid;
            find(left, mid - 1, houses, heaters);
        }
        else
        {
            find(mid + 1, right, houses, heaters);
        }
    }

    int findRadius(vector<int> &houses, vector<int> &heaters)
    {
        minVal = INF;
        sort(heaters.begin(), heaters.end());
        find(0, 1e9, houses, heaters);
        return minVal;
    }
};

// for test
int main()
{
    Solution s;

    return 0;
}