如何找到分組元素列表所需的最小組數量？

Question

例如：

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

我想找到最小組數，其中組中的每個成員都有 合格的差異，例如，彼此之間小於或等於2。

在這種情況下，我們可以看到答案應該是4，並且一種可能的解決方案是{1,2,3}，{4,6}，{8}，{11}。

如何編寫算法以查找最小數量？

此外，我們還可以在2個維度考慮：

還有點{（3,3），（3,6），（6,9）}的列表。什麼是長度爲3的平方的最小數量我需要用來覆蓋所有這些點數？答案應該是2。但如何通過編程來找到它？

我正在問這個問題，以解決Google Code Jam Practice Contest中的Square Fields問題，但解決這個問題的第一部分的任何答案對我來說已經足夠了。

Answer 1

對於1-D：按升序對元素進行排序，並通過將新組的左邊界設置爲尚未被任何組覆蓋的最小元素來貪婪地形成組。