Какой тип алгоритма я должен использовать?

Question

Допустим, у меня есть четыре группы

A [0, 4, 9]

В [2, 6, 11]

С [3, 8, 13]

D [7, 12]

Теперь мне нужно одно число из каждой группы (т.е. новая группа) E [число A, число B, число C, число D], так что разница междумаксимальное число в E и минимальное число в E должно быть минимальным. Какой тип проблемы? какой алгоритм графа будет лучше решить эту проблему? Спасибо заранее.

P.S: Я пытаюсь решить это в java и извините за неуказанный заголовок.

Edit: Наконец я нашел то, что я на самом деле ищет http://rcrezende.blogspot.in/2010/08/smallest-relevant-text-snippet-for.html

Answer 1

1. Объединить содержимое каждой группы в единый массив. Каждый элемент массива должен быть парой (число, имя группы).
2. Сортировка этого массива по номерам.
3. Продвиньте два итератора один за другим. Перенесите первый итератор, когда элементы не каждой группы находятся между этими итераторами. Переместите второй итератор, когда между этими итераторами есть элемент каждой группы. Подробнее см. this question.
4. Минимальное расстояние между итераторами определяет оптимальную результирующую группу (вам нужно только отказаться от ненужных элементов, если там есть несколько представителей той же группы).

---

Другой алгоритм:

1. Сортировать элементы каждой группы (если не сортируется уже).
2. Поместите пару (число, название группы) для наименьших элементов каждой группы в очередь приоритетов (min-heap, priority = number).
3. Удалите наименьший элемент из очереди и замените его следующим элементом из той же группы.
4. Повторите шаг 3, пока в какой-либо группе не осталось больше элементов. Вычислить max (queue) - min (queue) для каждой итерации, и если она меньше любого предыдущего значения, обновите группу, получившую лучшие результаты.

Answer 2

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

Например, если вы выбрали номер из A и B, вы можете выбрать два числа из C, которые являются ближайшими к этим двум номерам, используя любое другое число, не может дать лучших результатов.

• Для каждого элемента: называют его a, вы ищете число, близкие к интервалу (а, а)
• Теперь для каждой группы выбрать самые близкие номера (вы можете сделать это с двоичным поиск).Теперь у вас есть новый интервал поиска, либо (а, b1) или (b2, A)

Пример:

• Pick 4 из A, поиск близко к (4,4)
• A) Выберите 2 из B, ищите близко к (2,4)
• .... Выберите 3 из C, он находится в интервале. поиск вблизи (2,4)
• .... выбор 7 из D, интервал равен (2,7), расстояние равно 5.
• B) Выбрать 6 из B, найти рядом с (4,6)
• ....