algorithm - 如何找到对元素列表进行分组所需的最少组数？

Question

例如:

有一个元素列表，例如一个排序的整数列表 {1,2,3,4,6,8,11}。

我想找到最少数量的组，其中组中的每个成员都有一个 彼此之间的合格差异，例如彼此小于或等于 2。

在这种情况下，我们可以看到答案应该是 4，一种可能的解决方案是 {1,2,3},{4,6},{8},{11}。

求最小数的算法怎么写？

此外，我们可以在二维中考虑:

有一个点列表 {(3,3),(3,6),(6,9)}。我需要用多少个长度为 3 的正方形来覆盖所有这些点？这里的答案应该是2。但是如何通过编程找到呢？

我问这个问题是为了解决问题 Square Fields在 Google Code Jam 实践竞赛中，但解决此问题第一部分的任何答案对我来说都足够好。

Answer 1

对于一维:按升序对元素进行排序，并通过将新组的左边界设置为尚未被任何组覆盖的最小元素来贪婪地形成组。