Как рассчитать, что ни один поддиапазон не перекрывает друг друга, а весь поддиапазон охватывает весь диапазон в java?

У меня есть диапазон в java, реализованный как класс, который разделен на поддиапазоны. Реализация примерно следующая:

public class Range
{
   static public class Key implements Comparable<Key>
   {
      public int start;
      public int end;
      ...
   }

   Key range;
   SortedMap<Key, Range> subRange;
}

Я хочу создать функцию, которая гарантирует, что ни один поддиапазон не перекрывает друг друга, а объединенный диапазон поддиапазона полностью покрывает весь диапазон. Начало и конец каждого диапазона могут быть одинаковыми.

Пример действительного объекта:

Range: start 1, end 10
  subrange 1: start 1, end 2
  subrange 2: start 3, end 9
  subrange 3: start 10, end 10

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

РЕДАКТИРОВАТЬ:

Всем, кто интересуется реализацией:

В моем коде проверки я делаю следующие шаги:

  1. Преобразуйте отсортированную карту в массив
  2. Заставить первый и последний элементы покрыть начало и конец общего диапазона
  3. Перебирать элементы массива и исправлять зазоры или перекрытия между ними

Код для шага 3:

for (int i=0; i < (rangeArray.length - 1); i++)
{
    if (rangeArray[i].range.end < (rangeArray[i+1].range.start - 1) ||
        rangeArray[i].range.end >= rangeArray[i+1].range.start)
    {
        // Alternatively, lose the if and just force subrange to behave this way
        rangeArray[i].range.end = rangeArray[i+1].range.start - 1; 
    }
}

person avee    schedule 02.10.2010    source источник
comment
Avee, Вы можете выложить, пожалуйста, свой код? Мне нужно провести аналогичную проверку, и я не могу что-то придумать. Заранее спасибо.   -  person apatel    schedule 15.10.2010
comment
Привет, Амит, вот чем я закончил:   -  person avee    schedule 17.10.2010
comment
Привет, я обновил свой вопрос, включив в него фрагмент моей реализации, надеюсь, это поможет   -  person avee    schedule 17.10.2010


Ответы (2)


Поскольку ваша subRange карта отсортирована, вы можете перебирать ее и проверять, нет ли пробелов в последовательности от end до следующего start. И, конечно же, от вашей общей начальной точки до первой start и последней end до вашей общей конечной точки. Также рекурсивно примените эту проверку ко всем subRange.

Для этого ваша карта должна быть отсортирована по start, как в вашем примере.

person tangens    schedule 02.10.2010
comment
Это решает проблему, спасибо большое! Помимо проверки пропусков, я также проверяю на каждой итерации перекрывающиеся поддиапазоны. - person avee; 02.10.2010

Другой способ сделать это - просуммировать все диапазоны и сравнить ее с дельтой максимального и минимального значений по всем диапазонам. Если сумма больше или равна дельте, это означает, что есть пересечение.

person user1732055    schedule 09.10.2012