algorithm - 修改后的附近学校/邮局示例的贪婪算法方法

Question

我一直在尝试解决我教授笔记中的实践问题，但找不到最佳解决方案。以下是问题。

沿着一条东西向的街道，有 m 所公立学校，它们到街道西端的距离分别为 S[1] < S[2] < … < S[m]。除了 m 所学校外，还有 n 栋房子，它们到街道西端的距离分别为 H[1] < H[2] < … < H[n]。目前，任何家庭的学生都可以在 200 米的步行距离内找到一所学校。现在，因为预算不足，我们希望关闭一些学校。请设计一个 O(n+m) 贪心算法来选择最少数量的学校开放，这样任何家庭仍然可以找到其中一所选定的学校，步行距离在 200 米以内。你需要展示一个伪代码并证明你的算法的正确性。

Answer 1

高级思想

首先，我们知道解决方案总是存在的，只要不移除任何学校即可。

对于选择最少的学校，让我们换个角度思考:

For each house at h[i], think as a range [h[i]-200, h[i]+200] inclusively

因此，对于每个这样的范围，我们想在 s[j] 找到一些学校其中 h[i]-200 <= s[j] <= h[i]+200

同时 h[] & s[]排序好了，我们从最左边的房子开始看[h[0]-200, h[0]+200] ，我们必须为这所房子选择一所学校，直觉上，我们希望尽可能选择最右边的学校，因为这所学校有更高的机会 与隔壁房子分享

这个想法在一般情况下是正确的:

For range h[i], we always want to choose school which is already chosen school by h[i-?], or the rightmost non chosen school

正确性

设一个解是一个有序的学校集S , 未通过描述的方法找到

让我们的贪心法找到的解决方案是一组有序的学校 G

考虑 S[0]和 G[0] , S[0] <= G[0]因为我们为第一所房子选择了最合适的学校。然后要么

1. S[0] <= G[0] <= S[1] , 我们可以替换 S[0]通过 G[0]提供相同的集合大小
2. S[0] < S[1] < ... < S[X] <= G[0] <= S[X+1] , 我们可以替换所有 S[X] <= G[0]通过 G[0] ，它提供了更小/更优化的尺寸

(是的，案例 1 确实是案例 2 的子案例)

对于这两种情况，删除 G[0]和任何 S[X] <= G[0] ，场景与两个缩减集相同，我们可以递归地使用类似的参数，说我们的贪婪方法不会比任何可能的解决方案都差，这是最优的

伪代码

Pointer house_pointer = first house, school_pointer = first school;

for( each house ){
   if( NOT ( current school is chosen and within current house's range ) ){
       while(current school is NOT the rightmost school within range){
            school_pointer = current school = next school
       }
       mark current school chosen
   }
   house_pointer = next house
}

算法好像有两个循环，就是O(nm) ，但事实并非如此。对于这些使用双指针遍历数组的结构类型(例如 KMP algorithm )，通常您可以观察到每个元素被访问的最大 # 次。

对于房子，由于每次迭代都会移动到下一个房子，每个房子最多被访问 1 次。

对于学校来说，由于指针只向前移动而不会向后移动，所以每个学校最多也被访问 1 次，虽然在每个房屋迭代中分布不均匀(取决于实现，有些学校可能会访问 2 次但不是重要)

因此，结合两者，复杂度还是O(n+m)