Minifiying List of ranges as integer arrays

1
votes

I have code like this

public List<int[]> getMinifiedRanges(List<int[]> ranges) {
    for (int[] range : ranges) {

    }
}

My goal is to condense the list of ranges, represented by integer arrays which contain the ranges upper & lower bounds

ex. [100, 200] [250, 350] - this example would return the same input because nothing overlaps

[100, 200] [150, 350] [400, 500] - this would return [100, 350] [400, 500] because the second ranges lower bound is inclusive in the first range so the returned range would have its upper bound extended to 350 - notice how it returns only two arrays when the input was 3 arrays.

I am having trouble figuring out how to retrieve a previous range from a current range so that I could extend either the lower or upper bound.

3
javaalgorithmrange
Once you blend a range how can you get back the original? In your [100, 200] blended with [250, 350] --> [100, 350], I don't see how you can get back the original ranges from the output. Am I misunderstanding your question? – mba12
Sort by lower bound, iterate, if thecurrent range overlaps with the next one (recursively), then create a range using the current lower bound and the largest upper bound. – JB Nizet
@mba12 once the range is blended, I no longer would need to get the original range, the blended range is part of the final output, any further ranges that need to be blended follow the same procedure. – Robert Patch
For the thing you're actually having trouble with, either keep an int[] variable which stores the last result or use a "normal" (non-for-each) for loop (where accessing the last element is trivial). But this problem is much easier solved by separating start and end into the same list of ints and iterating over that. – Bernhard Barker
Possible duplicate of stackoverflow.com/questions/149577/… – BhalchandraSW

3 Answers

1
votes

Once you have the ranges sorted (by min, then by max), each set of overlapping ranges will be grouped together, so you can go through the list checking each range against the last merged range.

public static List<int[]> getMinifiedRanges(List<int[]> ranges) {
    List<int[]> minRanges = new ArrayList<>();
    if (ranges.isEmpty()) return minRanges;

    List<int[]> sorted = new ArrayList<>(ranges); // don't modify input list
    Collections.sort(sorted, Comparator.<int[]>comparingInt(r -> r[0]).thenComparingInt(r -> r[1]));

    int[] last = sorted.get(0);
    for (int[] next : sorted.subList(1, sorted.size())) {
        if (last[1] < next[0]) {
            minRanges.add(last);
            last = next;
        } else if (next[1] > last[1]) {
            last = new int[] { last[0], next[1] };
        }
    }
    minRanges.add(last);

    return minRanges;
}
0
votes

First you can split every range according to this form:

[a,b] range -> (a,1) and (b,2) pairs

Store these pair in a list then sort the list. After sorting you can iterate the list, when a pair like (x,1) comes increment a variable and when a pair like(x,2) comes decrement that variable. Places that varible went from 0 to 1 are starting indexes and places where variable went from 1 to 0 are finishing indexes.

0
votes

First blush, look for the places where the arrays stop intersecting. With this implementation you'll need to create the last range in the new, "merged" list...

List<int[]> ranges = new ArrayList<>(); //holds the original list of ranges
int[] current;
int[] previous;
List<int[]> merged = new ArrayList<>(); //will end up with the merged ranges
int max = ranges.size() - 1;
int start = 0;
for (int i = 1; i <= max; i++) {
  previous = ranges.get(i-1);
  current = ranges.get(i);
  if (current[0] > previous[1]) {
    merged.add(new int[] {ranges.get(start)[0], previous[1]});
    start = i;
  }
}
merged.add(new int[] {ranges.get(start)[0], ranges.get(max)[1]});