Я ищу хороший способ выравнивания (разделения) списка потенциально перекрывающихся числовых диапазонов. Проблема очень похожа на проблему этого вопроса: самый быстрый способ разделения перекрывающихся диапазонов дат и многие другие.
Тем не менее, диапазоны не только целые числа, и я ищу достойный алгоритм, который может быть легко реализован в Javascript или Python и т. Д.
Пример данных:
Пример решения:
Извините, если это дубликат, но я еще не нашел решение.
javascript
algorithms
python
Jollywatt
источник
источник
Ответы:
Идите слева направо, используя стопку, чтобы отследить, какого цвета вы находитесь. Вместо дискретной карты используйте 10 чисел в вашем наборе данных в качестве точек останова.
Начиная с пустого стека и устанавливая
start
в 0, цикл до конца:start
, и поместите его и все цвета с более низким рейтингом в стек. В своем плоском списке отметьте начало этого цвета.start
, и найти конец текущего цветаstart
конец этого цвета, вытолкните его из стека и проверьте следующий по цвету рейтинг.start
находится в пределах диапазона следующего цвета, добавьте этот цвет в плоский список, начиная сstart
.Это мысленный прогон данных вашего примера:
источник
Это решение кажется самым простым. (Или, по крайней мере, легче всего понять)
Все, что нужно, это функция для вычитания двух диапазонов. Другими словами, кое-что, что даст это:
Что достаточно просто. Затем вы можете просто перебирать каждый из диапазонов, начиная с самого низкого, и для каждого вычитать из него все диапазоны по очереди, по очереди. И там у вас есть это.
Вот реализация вычитателя диапазона в Python:
Используя эту функцию, все остальное можно сделать так: («span» означает диапазон, поскольку «range» - ключевое слово Python)
Это дает
[['red', [12.5, 13.8]], ['blue', [0.0, 2.0]], ['green', [2.0, 3.5]], ['green', [10.0, 12.0]], ['yellow', [3.5, 6.7]], ['orange', [6.7, 10.0]]]
, что правильно.источник
Если данные действительно похожи по объему на ваши примеры данных, вы можете создать карту следующим образом:
Затем просто пройдите по этой карте, чтобы сгенерировать диапазоны
Чтобы работать, значения должны быть в относительно небольшом диапазоне, как в ваших выборочных данных.
Редактировать: для работы с истинными числами с плавающей запятой используйте карту для создания высокоуровневого отображения, а затем обратитесь к исходным данным для создания границ.
источник
Вот относительно простое решение в Scala. Не должно быть слишком сложно портировать на другой язык.
apply
беретSet
из всех примененных диапазонов, находит перекрытия, затем возвращает новый набор минус перекрытия и плюс новый диапазон и новые разделенные диапазоны.foldLeft
неоднократно звонитapply
с каждым входным диапазоном.источник
Просто держите набор диапазонов, отсортированных по началу. Добавьте диапазон, который охватывает все (-oo .. + oo). Чтобы добавить диапазон r:
источник