如何在java中验证重叠否

Question

我有动态渲染行.我们有像FROM TO这样的领域.

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-each中找到任何重叠,那么就没有重叠.

因此,对于您给出的两个测试用例,这就是它的工作方式:

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>