2

Имеется диапазон чисел (тип double) от 0 до 500. В процессе работы программы создаются маленькие интервалы, например от 4.537 до 7.654, или от 121.346 до 156.234

Необходимо в большом диапазоне (0-500) "зарезервировать" эти "маленькие" интервалы.

И когда образуется очередной "маленький" интервал, проверить, а не "занято ли место" в "большом" диапазоне. Если "занято", то "занять" хотя бы остаток.

Например: кто-то занял в большом диапазоне от 20 до 30, а новые данные хотят занять от 25 до 40, тогда должна отметится область от 20 до 40 как занятая.

Как лучше это организовать?

5
  • Только сейчас заметил слово "в массиве" в заголовке. А это принципиально, нужно именно массив использовать?
    – m. vokhm
    4 дек 2016 в 19:54
  • Не обязательно, просто мне кажется что с ним проще всего работать. А вообще я кажется придумал как сделать. Я сделаю массив из типов boolean? Размер массива 500*100 = 50000. Значение начала диапазонов и конца просто умножу на 100 или 1000, чтобы запятую не потерять, а потом разделю обратно, когда значение буду брать.
    – kaaa
    6 дек 2016 в 21:19
  • Дело хозяйское, но мне кажется, то, что я предложил - и проще, и гибче, и надежней. Если вам, например, понадобится занять интервал 0.00001234 .. 0.00002384736, что вы будете делать? А если завтра захочется использовать диапазон не от 0 до 500, а от -1000000 до 1000000 - сколько памяти вам надо будет докупить в машину?
    – m. vokhm
    7 дек 2016 в 12:02
  • Прикиньте расход памяти и время выполнения для того и другого случая. Если вам надо проверить на занятость весь диапазон от 0 до 500 с шагом 0.001, вам надо будет сделать 500 000 проверок?
    – m. vokhm
    7 дек 2016 в 12:07
  • Да, ваш вариант более оптимален, согласен.
    – kaaa
    7 дек 2016 в 14:21

1 ответ 1

1

Решений может быть много, как лучше организовать - в общем случае нельзя сказать, поскольку критерии "лучшести" могут быть разные. Одно из возможных решений (первым пришедшее в голову): представлять занятые диапазоны в виде пар чисел '[началоДиапазона, конецДиапазона]', например Map.Entry<Double, Double> и хранить их в упорядоченном словаре, можно в 'TreeMap'.

При этом код для резервирования диапазона может быть примерно таким:

Map.Entry<Double, Double> occupy(Double rangeStart, Double rangeEnd) {
  Map.Entry<Double, Double> floor = map.floorEntry(rangeStart);
  if (floor != null && floor.getValue() >= rangeStart) {
    map.remove(floor.getKey()); 
    rangeStart = Math.min(floor.getKey(), rangeStart);
    rangeEnd = Math.max(floor.getValue(), rangeEnd);
  }
  Map.Entry<Double, Double> ceiling = map.ceilingEntry(rangeStart);
  if (ceiling != null && ceiling.getKey() <= rangeEnd) {
    map.remove(ceiling.getKey()); 
    rangeEnd = Math.max(ceiling.getValue(), rangeEnd);
  }
  map.put(rangeStart, rangeEnd);
  return map.ceilingEntry(rangeStart);
}

А код для проверки того, занят или нет интересу.щий вас диапазон может выглядеть как-то так:

/** Checks if the whole range is occupied -- no free areas */
boolean isFree(Double rangeStart, Double rangeEnd) {
  Map.Entry<Double, Double> floor = map.floorEntry(rangeStart);
  if (floor != null && floor.getValue() >= rangeStart) return false;
  Map.Entry<Double, Double> ceiling = map.ceilingEntry(rangeStart);
  if (ceiling != null && ceiling.getKey() <= rangeEnd) return false;
  return true;
}

/** Checks if the whole range is free -- no occupied areas */
boolean isOccupied(Double rangeStart, Double rangeEnd) {
  Map.Entry<Double, Double> floor = map.floorEntry(rangeStart);
  if (floor != null && floor.getValue() >= rangeEnd) return true;
  return false;
}

Рабочий сниппет с парой дополнительных методов и минималистским набором тестов можете посмотреть на http://ideone.com/3arRnM. За верность и красоту кода не ручаюсь - идея не очень-то продумана и реализована наспех. Думайте, наводите красоту и тестируйте дальше сами.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.