题目重点：排序后从最小未分配值建立最长可行组，以交换论证证明贪心。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练合同可任意重新分组，组非空，差指绝对差；maxdiff非负。
- 若要求原数组连续分段，这是不同合同；本文排序解不适用。
解题路线
- 一维组内任意两值差不超过d等价于max-min≤d。排序后以最小未分配值x为组起点，吸收所有≤x+d的剩余值，再建下一组。
- 下界与交换：任何覆盖最小剩余x的组都不能包含>x+d；将[x,x+d]中尚未分配值全部移入这个组仍合法，不增加组数。删去该组归纳求剩余，故贪心最优。
- 不要只比较相邻值。相邻差均小并不能证明首尾差小；组边界必须固定首元素。实现返回组本身，便于同时核对覆盖、重复值和范围。
- 若必须保留索引，可先排序(value,index)再输出索引；重复值代表不同输入元素，不能先set去重。
手动走一遍
训练例[3,1,7,2,8]，d=2：排序后[1,2,3]与[7,8]共2组。[1,3,5]的相邻差2，但d=2不能一组容纳三项。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def minimum_groups(values, maxdiff):
"""Groups may reorder elements; pairwise absolute difference <= maxdiff."""
if maxdiff < 0:
raise ValueError("maxdiff must be nonnegative")
groups = []
for value in sorted(values):
if not groups or value - groups[-1][0] > maxdiff:
groups.append([])
groups[-1].append(value)
return groups
复杂度
O(n log n)时间、示例O(n)额外空间；已排序数据O(n)扫描。
易错点与追问
容易失分的边界
- 仅比较相邻元素，允许范围连锁膨胀。
- 隐式要求连续原下标却使用排序。
- 去掉重复输入导致覆盖数错。
继续深挖
- 返回原始下标组怎样做？
- 每组最多K项还能怎样贪心？
- 元素是二维点时为何该证明失效？
