Greedy - 在一定距离内找到小屋
Greedy - Locate Cottage Boxes within a distance
某机构想要定位道路上的箱子。我们在路上有小屋。每间小屋都有自己的包厢。每个小屋的盒子都存在于这条路上的 x_1、x_2、...、x_n 英里处（这些值可以假定为不同的整数，以英里为单位记录距指定地点的距离起源）。我们的目标是尽量减少箱子的数量，同时确保没有小屋距离 closest/nearest 箱子超过 K 英里。
直觉：对于这个贪心算法，我想一次看一个小屋，按某种顺序，然后做一个贪心选择（some greedy choice）来选择盒子的位置。我想我首先应该做的是对小屋位置进行排序。但我正在为贪婪的选择而苦苦挣扎。
假设 x_i 是路上小屋的距离（而不是箱子的位置，因为它们没有给出并且应该被找到）。不失一般性，x_i 被排序。然后把第一个盒子放在路边距离x_1 + K的地方。这一定是最优的，因为在距离 x_1 距离 K 内必须有一个盒子，无论你把它放在哪里，它都不能提供比距离 x_1 最远时更多的小屋（因为有x_1之前没有小屋）。
继续...让 a_1 成为距离盒子 K 之外的第一个小屋，并将第二个盒子放在沿路距离 x_{a_1} + K 的位置。
一般来说，如果你放了 i 个盒子，让 a_i 是距离盒子 K 以外的第一个房子，然后把盒子 i+1 放在距离 x_{a_i } + K 沿路.
某机构想要定位道路上的箱子。我们在路上有小屋。每间小屋都有自己的包厢。每个小屋的盒子都存在于这条路上的 x_1、x_2、...、x_n 英里处（这些值可以假定为不同的整数，以英里为单位记录距指定地点的距离起源）。我们的目标是尽量减少箱子的数量，同时确保没有小屋距离 closest/nearest 箱子超过 K 英里。
直觉：对于这个贪心算法，我想一次看一个小屋，按某种顺序，然后做一个贪心选择（some greedy choice）来选择盒子的位置。我想我首先应该做的是对小屋位置进行排序。但我正在为贪婪的选择而苦苦挣扎。
假设 x_i 是路上小屋的距离（而不是箱子的位置，因为它们没有给出并且应该被找到）。不失一般性，x_i 被排序。然后把第一个盒子放在路边距离x_1 + K的地方。这一定是最优的，因为在距离 x_1 距离 K 内必须有一个盒子，无论你把它放在哪里，它都不能提供比距离 x_1 最远时更多的小屋（因为有x_1之前没有小屋）。
继续...让 a_1 成为距离盒子 K 之外的第一个小屋，并将第二个盒子放在沿路距离 x_{a_1} + K 的位置。
一般来说，如果你放了 i 个盒子，让 a_i 是距离盒子 K 以外的第一个房子，然后把盒子 i+1 放在距离 x_{a_i } + K 沿路.