CODEWITHSUNDEEP
javaarraysloopsfor-looparraylist
Simona Anomiss
Simona Anomiss

Reputation: 23

Insert Elements to an ArrayList like intervals java

First example: I have ranges

[10, 30] [80, 100] [150, 200]

I have to insert for example [90, 120]. After, insertion, the resulting ranges will be:

[10, 30] [80, 120] [150, 200]

This happens because the range [100, 120] was not in the original range, so 100 gets increased to 120, but 90 will not be added because is in the range of 80 to 120.

Similarly, if I were to add [50, 90] to the original range, the resulting range would be

[10, 30] [50, 100] [150, 200]

This time, the lower bound gets reduced to 50, widening the range on the lower side, but the 90 is ignored because it is already in the range [80, 100]. I am attempting to make a class to represent this problem.

Currently, I take the start numbers into ArrayListStart [10, 80, 150] and the end numbers into ArrayListEnd [30, 100, 200] and I loop through them. I compare if it is smaller of the smallest number etc.

However, I cannot seem to get this method to work. Can anyone help me solve this problem?

Upvotes: 1

Views: 594

Answers (3)

nitegazer2003
nitegazer2003

Reputation: 1193

class Range { int left, right; }

ArrayList<Range> list;

boolean intersects(Range r1, Range r2) { /* tests if 2 ranges intersect */ };
Range join (Range r1, Range r2) { /* joins two ranges */ }

void add(Range r) {
    int i;
    for (i=0; i < list.size(); i++) {
        if (intersects(list.get(i), r)) {
            list.set(i, join(list.get(i), r));
            while (i + 1 < list.size() && intersects(list.get(i), list.get(i+1)) {
                Range rtemp = list.remove(i+1);
                list.set(i, join(list.get(i), rtemp));
            }
            break;
        }
    }
    if (i == list.size()) {
        list.add(r);
    }
}
  1. Test from smallest to largest range, if none intersect, add to the end
  2. If any existing range intersects, merge it with the new range.
  3. Then test whether the merged range now intersects with the next existing range in the list, if so, merge it. Repeat 3 until the new range does not intersect the next range.

Upvotes: 0

lbalazscs
lbalazscs

Reputation: 17784

Check out the Guava Range class and the implementations of the RangeSet interface.

Implementations that choose to support the add(Range) operation are required to ignore empty ranges and coalesce connected ranges.

Upvotes: 1

Tavo
Tavo

Reputation: 3161

I assume you have something like this:

private Integer[] minArray = new Integer[]{10,80,150};
private Integer[] maxArray = new Integer[]{30,100,200};

So what you are looking for is something like this:

private void changeRange(int min, int max) {
    boolean found = false;
    int position=0;
    while(position<minArray.length && !found) {
        if(min>minArray[position] && min<maxArray[position]) {
            found = true;
            if(max>maxArray[position]) {
                maxArray[position] = max;
            }
        } else if(max>minArray[position] && max<maxArray[position]) {
            found = true;
            if(min<minArray[position]) {
                minArray[position] = min;
            }
        } else {
            position++;
        }
    }
}

So if your min is between a value in minArray and maxArray, change the value in maxArray for max (and min in case max is between minArray and maxArray).

You don't state what happens if the values are not in one of your ranges, so I have assumed nothing. Else, I'm sure you can figure out from here.

Upvotes: 0

Related Questions