How to validate overlapping no in java

I Have dynamically render row. WE have fields like FROM TO.

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

It cannot accept this combination row.. That means no number should be overlapping.

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

This combination is allowed.the row may also increased.

I need need to write a validation for this overlapping. Can any 1 help to solve this problem.

This is the code, wat i tried,

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).get开发者_如何学JAVAStartValue().equals(a.get(l).getEndValue())
                || b.get(j).getStartValue() < a.get(l).getEndValue())))
        {
            System.out.println("INNN*************");
            count++;
        }
    }
}
System.out.println("count********" + count);

Your algorithm is O(N^2); in fact you can easily do this in O(N log N) as follows.

• Sort intervals by their upper bound: O(N log N)
• For-each interval: O(N)
  • If this interval's lower bound is lower than the previous interval's upper bound, then there's overlap
• If you didn't find any overlap in the for-each, then there's no overlap.

So for the two testcases you've given, this is how it'll work:

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!

To do this in Java, you'd want to use:

• class Interval implements Comparable<Interval>
• List<Interval> and then Collections.sort
  • Or you can use TreeSet<Interval>

Here's a little test case:

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));

    }
}

And a class that passes the test:

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;
    }

}

pseudocode:

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

clear?

You can create and boolean array with the size of the max number you can get, say bool mem[MAX_SIZE], then for each of those rows, you will set the according TO-FROM range in that boolean array to true, true meaning that this position is already occupied.

Something like this:

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

then, when you want to process the rows, as your example states, a sufficient condition to signal an illegal operation is that either TO or FROM overlaps an already processed interval

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

If your MAX_SIZE is relatively big, then the array will get bigger, but it does save you processing time over some nested for loops.

I would do it like so:

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;
}

This assumes that the start of an interval is always smaller than the end of an interval. It does as little checks as possible.

It looks like a lot of the answers here are pretty spot-on. There is, however, a well understood data-structure for this that might be of use to you: Interval Tree.

Set numbers = new HashSet()

while more numbers { read next number; if not exist in numbers continue else fail validation; }

(or I completly misunderstood the question...)