Получить наибольшее подмножество целых чисел с определенным минимальным расстоянием/разностью

Question

У меня есть набор целых чисел или пример: {1,3,4,5,10} теперь я хочу самый большой (самый большой = большинство элементов) Подмножество, где каждый элемент имеет минимальное расстояние/разность между элементами.

Например с множеством {1,3,4,5,10} и минимальное расстояние 2 результат может быть:

{1,3,5,10}

или для расстояния 3 :

{1,5,10}

существует ли (хороший эффективный /) алгоритм для решения этой проблемы?

Answer 1

Это определенно не проблема NP-полной.

На самом деле это частный случай классической Interval Scheduling проблемы, в то время как в обычной интервальной задаче планирования, длина не фиксирован

Вот в ваших проблемах, вы можете просматривать каждое число является время начала интервала, и каждый интервал имеет «минимальное расстояние» в качестве длины интервала.

Каждый интервал имеет время окончания, которое является временем начала интервала + длина

Таким образом, решение будет

1 Сортировка весь интервал по времени окончания.

2 Пройдите через них в отсортированном порядке по одному, добавьте интервал к набору результатов, который совместим со всеми существующими интервалами в результирующем наборе.

Это решение является оптимальным и имеет сложность времени O (nlogn).

Вы можете найти доказательства и информацию о других жадных алгоритмах в приведенной выше ссылке.

Answer 2

Что-то в этом стихе:

1) Сортировка ввода.

2) Пройдите через вход и отметьте каждый элемент количеством элементов, которые они исключили бы из набора, если бы они были выбраны.

3) Выберите из доступных элементов, в порядке, с наименьшей отметкой.

4) Удалите исключенные элементы.

5) Повторить 3) и 4)

Итак, на вашем примере:

1 3 4 5 10  - difference 3 

Шаг 1 уже сделано, идя к шагу 2, мы получим:

1 3 4 5 10 
1 3 2 2 0 

Объяснение - если мы выберем 1, мы исключаем 1 номер -3; если мы выбираем 3, мы исключаем 3 числа -1,4 и 5, и так далее ...

Следующие шаги:

• Pick 10, удалите ничего. - 1 3 4 5 (10)
• Pick 1, удалить 3. - (1) 4 5 (10)
• Pick 4 (или 5), удалите 5 (или 4) - 1 4 10

Я не гарантирую это работает, но это начало. ..

Answer 3

Да, этот жадный алгоритм дает оптимальные решения. Сканирование целых чисел в отсортированном порядке, взятие каждого целого числа, если предыдущее целое число было достаточно далеко. Правильность следует индуктивным доказательством того, что для любого решения S и любого целого числа u жадное решение выбирает по крайней мере столько целых чисел ≤ u, что и S.