Как проверить перекрытие нет в Java

Question

У меня динамически отображается строка. У нас есть поля, такие как ОТ.

For eg: From     TO
        2        10,
        2        3,
        8        12

Он не может принять эту комбинацию строк. Это означает, что ни одно число не должно совпадать.

For eg: From     TO
        2        10,
        0        1,
        11       12

Эта комбинация разрешена. Строка также может увеличиваться.

Мне нужно написать подтверждение для этого перекрытия. Может ли 1 помочь решить эту проблему.

Это код, который я пробовал,

List<AppHrVacationAccrualRuleDefinition> a = new ArrayList<AppHrVacationAccrualRuleDefinition>();
List<AppHrVacationAccrualRuleDefinition> b = new ArrayList<AppHrVacationAccrualRuleDefinition>();

a=ruleDefinition;
b=ruleDefinition;

int count = 0;
int k = 1;

for (int l = 0; l < a.size(); l++)
{
    for (int j = k; j < b.size(); j++)
    {
        if (((a.get(l).getStartValue().equals(b.get(j).getEndValue()) || 
                a.get(l).getStartValue() < b.get(j).getEndValue())) && 
                ((b.get(j).getStartValue().equals(a.get(l).getEndValue())
                || b.get(j).getStartValue() < a.get(l).getEndValue())))
        {
            System.out.println("INNN*************");
            count++;
        }
    }
}
System.out.println("count********" + count);

Answer 1

Ваш алгоритм O(N^2); на самом деле вы можете легко сделать это в O(N log N) следующим образом.

• Сортировать интервалы по их верхней границе: O(N log N)
• Для каждого интервала: O(N)
  • Если нижняя граница этого интервала ниже верхней границы предыдущего интервала, то это перекрытие
• Если вы не нашли перекрытия в for-каждому, тогда перекрытия нет.

Итак, для двух тестовых случаев, которые вы дали, вот как это будет работать:

Input:
  (2, 10), (2, 3), (8, 12)

Sorted by upper bound:
  (2, 3), (2, 10), (8, 12)
      |____|
      FOUND OVERLAP!

Input:
  (2, 10), (0, 1), (11, 12)

Sorted by upper bound:
  (0, 1), (2, 10), (11, 12)
      |____|   |____|
        OK!      OK!        NO OVERLAP!

Чтобы сделать это на Java, вы должны использовать:

• class Interval implements Comparable<Interval>
• List<Interval>, а затем Collections.sort
  • Или вы можете использовать TreeSet<Interval>

Answer 2

Вот небольшой тестовый пример:

package playground.tests;

import java.util.ArrayList;
import java.util.List;

import junit.framework.TestCase;
import playground.Range;

public class NonoverlappingRangeListsTest extends TestCase {
    public void testOverlap() throws Exception {
        assertFalse(new Range(0, 5).overlaps(new Range(6, 7)));
        assertTrue(new Range(0, 5).overlaps(new Range(3, 7)));
        assertTrue(new Range(0, 5).overlaps(new Range(7, 3)));
        assertTrue(new Range(0, 5).overlaps(new Range(-1, 0)));
        assertTrue(new Range(0, 5).overlaps(new Range(5, 6)));
        assertTrue(new Range(0, 5).overlaps(new Range(2, 3)));
    }

    public void testIsNonoverlappingList() throws Exception {
        List<Range> list = new ArrayList<Range>();
        assertTrue(Range.isNonoverlapping(list));
        list.add(new Range(0, 5));
        list.add(new Range(6, 7));
        assertTrue(Range.isNonoverlapping(list));
        list.add(new Range(2, 3));
        assertFalse(Range.isNonoverlapping(list));

    }
}

И класс, который проходит тест:

package playground;

import java.util.List;

public class Range {

    private final int from;

    private final int to;

    public Range(int from, int to) {
        this.from = Math.min(from, to);
        this.to = Math.max(from, to);
    }

    public boolean overlaps(Range that) {
        return this.from <= that.to && that.from <= this.to;
    }

    public static boolean isNonoverlapping(List<Range> ranges) {
        for (int i = 0; i < ranges.size(); i++)
            for (int j = i + 1; j < ranges.size(); j++)
                if (ranges.get(i).overlaps(ranges.get(j)))
                    return false;
        return true;
    }

}

Answer 3

Похоже, что многие ответы здесь довольно точные. Однако для этого есть хорошо понятная структура данных, которая может вам пригодиться: Дерево интервалов .

Answer 4

Я бы сделал это так:

public boolean overlap(List<Interval> intervals) {
    int countMinusOne = intervals.size() - 1;

    for (int i = 0; i < countMinusOne; i++) {
        Interval first = intervals.get(i);

        for (int j = i + 1; j <= countMinusOne; j++) {
            Interval second = intervals.get(j);

            if (second.getStart() <= first.getEnd() &&
                second.getEnd() >= first.getStart()) return true;
        }
    }

    return false;
}

Предполагается, что начало интервала всегда меньше конца интервала. Он делает как можно меньше проверок.

Answer 5

Вы можете создать и логический массив с размером максимального числа, которое вы можете получить, скажем, bool mem[MAX_SIZE], затем для каждой из этих строк вы установите соответствующий диапазон TO-FROM в этом логическом массиве на true, истинный смысл в том, что эта должность уже занята.

Примерно так:

void mark(int to, int from){
  for(int i=to; i<= from; i++)
     mem[i] = true; //falls into an already-existing interval
}

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

boolean isOverlap(int to, int from){
   if(mem[to] == true || mem[from] == true)
       return true;
}

Если ваш MAX_SIZE относительно большой, то массив станет больше, но это сэкономит вам время обработки по сравнению с некоторыми вложенными циклами.

Answer 6

псевдокод:

foreach i1 in interval
   foreach i2 in interval
      if (i1 != i2)
         if (overlap(i1, i2))
            return true;

очистить

Answer 7

Установить числа = новый HashSet ()

, в то время как больше чисел {читать следующий номер;если не существует в числах, продолжайте, если проверка не пройдена;}

(или я совершенно не понял вопроса ...)