Как найти минимальное количество групп, необходимых для группировки списка элементов?

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. Но как найти его по программированию?

Я задаю этот вопрос для решения вопроса Square Fields в Google Code Jam Practice Contest, но любой ответ, решающий первую часть этого вопроса, достаточно для меня.

Answer 1

Для 1-D: сортируйте элементы по возрастанию и жадно формируйте группы, установив левую границу новой группы как самый маленький элемент, еще не охваченный какой-либо группой.