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

Question

У меня есть диапазон в 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. Forceпервый и последний элемент, охватывающий начало и конец общего диапазона
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; 
    }
}

Answer 1

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

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

Answer 2

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