岩石最少分组问题：排序贪心策略的可行性验证

问题明确 #

给定岩石重量列表weights和整数maxVariance，要求分组后每组内任意两块岩石重量差不超过maxVariance，求最少分组数。比如示例中：

weights = [5,3,2,4,6]
maxVariance = 2

排序后为[2,3,4,5,6]，贪心分组得到[2,3,4]和[5,6]，共2组，确实是最优解。

贪心策略的具体做法 #

• 先将所有岩石重量按升序排序
• 从第一个元素开始，把它作为当前组的基准，尽可能把后面所有满足重量 ≤ 基准 + maxVariance的岩石都纳入当前组
• 碰到第一个不满足条件的元素时，开启新组，重复上述步骤

为什么这个策略能得到最少分组？ #

用反证法就能清晰证明：
假设存在一种分组方式，组数比贪心策略的结果更少。

设贪心分出来的组为G1, G2, ..., Gk，假设最优分组为H1, H2, ..., Hm，且m < k。

从第一个元素开始对比：

• 贪心的G1是包含第一个元素的最大可能组——也就是直到第一个超过基准+maxVariance的元素为止，能容纳的所有岩石
• 最优分组的H1必然包含第一个元素，但它的覆盖范围不可能比G1大（否则贪心策略一定会把那些元素都放进G1），也就是说H1最后一个元素的位置不会比G1的靠后

接下来看剩余岩石：H1剩余的岩石数量肯定比G1剩余的多，因为H1覆盖的范围更小。以此类推，每一步最优分组剩余的岩石都不会比贪心策略的少，那最终需要的组数不可能比贪心策略更少，这与假设矛盾。

因此，贪心策略得到的分组数就是最少的，完全可行。

补充说明 #

这个策略的时间复杂度主要由排序决定，为O(n log n)，后续遍历仅为O(n)，整体效率很高，适合处理这类问题。

内容的提问来源于stack exchange，提问作者Nathan