java - 如何在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>