新鲜狗狗店面，感觉是跪了啊。。。

刚面完，感觉是跪了。。。。第二问说思路的时候估计思路不对，对面一直说不懂。。。
写到45min的时

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

给定m，求最小的n。第二问给定n，求最小的m
祝好运

我定义供暖站覆盖范围m是指覆盖m个连续整数[left, left+m-1]。若是指单位区间个数的话类似，不影响算法实现。
第一个问给定m，求最小的n。这个应该用greedy。对于给定的每个station的覆盖范围[left, left+m-1] (m给定)，首先找最左边还没有覆盖的第一个房子，用station的左边缘覆盖（这样还可以同时覆盖右边其它的房子），然后看还有没有未被覆盖的房子。若没有的话算法就完成，否则继续。最差情况时间复杂度O(N) (N为房子个数)，当房子间距比起station覆盖范围来说非常稀疏时。
第二问给定n，求最小的m。利用第一问已有的方法对station覆盖范围做binary search. 下限当然=1，上限=最两边的房子间距+1. 因为房子给定是在1D array上，所以最大间距范围不过int范围，这样外层binary search 时间O(log(int range))我觉得可以按常数对待吧，内部每次搜索调用第一题的O(N)算法，最终时间复杂度也为O(N)。

1. // assume houses is a sorted array
   
2. // a station covers [left, left+m-1]
   
3. int minStation(vector<int>& houses, int m) {
   
4.   if (m <= 0) return INT_MAX; // cannot cover
   
5.   int n = 0; // number of stations needed
   
6.   int left = INT_MIN; // left boundary of current coverage
   
7.   auto pos = houses.begin(); // position of first uncovered house
   
8.   while ((pos = upper_bound(pos, houses.end(), left+m-1)) != houses.end()) {
   
9.      n++;
   
10.      left = *pos; // left boundary of next coverage
    
11.   }
    
12.   return n;
    
13. }
    
14. 
    
15. int minCoverage(vector<int>& houses, int n) {
    
16.   int nHouses = houses.size();
    
17.   if (nHouses <= n) return 1; // if we have sufficiently many stations
    
18.   int minCover = 1, maxCover = houses[nHouses-1] - houses[0];
    
19.   while (minCover < maxCover) {
    
20.     int mid = (minCover+maxCover)/2;
    
21.     if (minStation(houses, mid) <= n) maxCover = mid;
    
22.     else minCover = mid + 1;
    
23.   }
    
24.   return minCover;
    
25. }

复制代码

补充内容 (2016-10-28 09:59):
C++ API: ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)是在范围[first, last)中寻找第一个大于val的元素并返回iterator. 若找不到就返回last.

wangyiduo999 发表于 2016-10-31 05:44
再准确点是mn^2的复杂度，m = 多少供暖站， n = 房子的个数

谢谢，我明白了。是因为一个既然最佳覆盖方案的供暖站之间是不会有重叠覆盖的，所以用i个站盖住j个房子的最佳方案一定是前(i-1)个站盖住了左边的连续某k个房子(0<k<j)，然后最后一个站一定盖住了剩余靠右边的(A.size()-k)个房子。这个时间O(站个数×房子个数^2)，空间最优到O(房子个数)因为dp(i, *)只依赖于dp(i-1, *).
看来你定义的“覆盖”是用覆盖半径的长度，不过这怎么定义不影响实现，而且题目也没有明确说什么是“覆盖范围”。

补充内容 (2016-10-31 09:19):
就是这个算法复杂度比较高

syjohnson 发表于 2016-10-30 12:23
请问第二题用binary search的话怎么判断当前猜的m是大是小呢？难道每次都要再把array of house再扫一遍吗

应该是再扫一遍，因为对于不同的m来说，这个覆盖的格局可能会彻底改变。利用第一问已有的方法对station覆盖范围做binary search. 下限当然=1，上限=最两边的房子间距+1. 因为房子给定是在1D array上，所以最大间距范围不过int范围，这样外层binary search 时间O(log(int range))我觉得可以按常数对待吧，内部每次搜索调用第一题的O(N)算法，最终时间复杂度也为O(N)。我自己写了一下在24层。

楼主可以说说思路吗，我一个小时后面

zhan8803705 发表于 2016-9-1 03:13
楼主可以说说思路吗，我一个小时后面

第二问一直在提示说用第一问。。。第一问贪心已经就行

第一问greedy第二问递归？

补充内容 (2016-9-1 08:44):
第2问递归可以优化成2D DP，更新m[i, l]计算第1个到第i个房子放l个供热站需要的最小的m.
这个做法理论上可能没有二分搜索好（但因为剪枝实际上可能还是够快），不过算一种标(无）准（聊）解法...

tcswdys 发表于 2016-9-1 03:16
第二问一直在提示说用第一问。。。第一问贪心已经就行

用第一问的话想到一个略傻的方法
把房子pairwise的距离从小到大排序，作为candidate的m值。然后一个个试能不能用n个供热站cover

tcswdys 发表于 2016-9-1 03:16
第二问一直在提示说用第一问。。。第一问贪心已经就行

第一问greedy就行，很直接。
第二问直接考虑的话也有很多奇奇怪怪的算法，如果面试官提示就用第一问的话那就binary search就行了。
假如第一问的答案是 n=f(m), 这f(m)肯定是递减的， 那第二问就是找最小的满足 f(m)<=n 的m。这种算法要调用第一问多次，是不是最优就不知道了。不过既然面试官要用第一问的结果，应该不会效率太差吧。。。

多谢楼主分享，想进一步问一下题意，输入是提供房子的一维坐标，比如[1,3,5,7,9,10]
这里的供热站n个和m米的覆盖范围，请问供热站是可以任意选取地方建设的吗？如果供热站是可以任意移动的，那两问都用贪心就好了啊，
如果供热站的是给定位置的，即供热站的位置坐标是定死的，那么感觉贪心也可以做啊，
另外这个供热覆盖m米指的应该是前后吧，比如一个供热站坐标是1,m为3，那么这个供热站覆盖的房子可以[-2,4]，对吗？

aangel 发表于 2016-9-1 05:50
多谢楼主分享，想进一步问一下题意，输入是提供房子的一维坐标，比如[1,3,5,7,9,10]
这里的供热站n个和m米 ...

第二问怎么贪心？

hxtang 发表于 2016-8-31 12:25
用第一问的话想到一个略傻的方法
把房子pairwise的距离从小到大排序，作为candidate的m值。然后一个个试 ...

我最开始想到的大致也是这样， 但好像不行。。这样只能保证一个供电站cover至少2个房子，如果供电站总数n很小，房子很多，那么一个供电站需要cover>=2个房子。。

xpli521 发表于 2016-9-1 07:53
我最开始想到的大致也是这样， 但好像不行。。这样只能保证一个供电站cover至少2个房子，如果供电站总数n ...

如果m是房子i到j的距离，那么m自动cover了i到j之间的所有房子，cover的房子可能是>2的。
比如i是第一幢房子，j是最后一幢房子，那么n＝1也没关系，因为m cover了所有房子。
最后搜具体的m值的时候像ytsr说的可以二分。