Best algorithm to find intersection and overlapping of ranges and storing the resultant range set

Question

I have ranges let's say

1. 1-10
2. 20-40
3. 30-50
4. 55-65
5. 65-80
6. 75-90
7. 95-100

As in this example 20-40 and 30-50 intersects instead of storing both I need to store it as 20-50.

Then instead of 55-65,65-80 and 75-90 I want to store 55-90 alone.

So the result set would be like this

1. 1-10
2. 20-50
3. 55-90
4. 95-100

I have these values in redis and the Structure which I store them in Java are arrays a start array and end array.

My solution :

for int i =0; i< length-1 ; i++
    for int j=i+1;j<length; j++
        if start[i] <= start[j] && end[i] >= start[j]
            store the min max in start and end array and remove the other two entries and proceed

I found this as O(n log n) is there any better algorithm to do this?

Any suggestions in the data structure both in Java and redis and the approach or algorithm for processing this would be great.

Thanks

Answer 1

If the intervals are sorted by the start position, there is a very simple linear algorithm to merge the intervals. Sorting takes O(nlogn), so the overall time complexity is the same. If the input is not sorted, I believe general algorithms still take O(nlogn). Sorting is usually faster because it is associated with a small constant. It is the more efficient solution.

Here is an implementation in javascript, just to give you an idea. You can translate to java or can run it with node.js:

function merge_intervals(a)
{ // this function save the result IN PLACE
    if (a.length == 0) return;
    var st = a[0][0], en = a[0][1], k = 0;
    for (var i = 1; i < a.length; ++i) {
        if (a[i][0] > en) { // a new interval
            a[k++] = [st, en];
            st = a[i][0], en = a[i][1];
        } else en = a[i][1] > en? a[i][1] : en;
    }
    a[k++] = [st, en]; // add the last interval
    a.length = k; // discard the rest
}

// intervals are half-close-half-open, like C arrays
var a = [[1,10], [20,40], [30,50], [55,65], [65,80], [75,90], [95,100]];
// sort the intervals based on start positions
a.sort(function(x,y) { return x[0]-y[0] });

merge_intverals(a);
for (var i = 0; i < a.length; ++i)
    console.log(a[i].join("\t"));

Answer 2

I think the ranges may not be always in order. Of course, the code may not be best but it's functional

import java.util.*;


class Interval {
    int lo;
    int hi;
    Interval() {
        lo = 0;
        hi = 0;
    }

    Interval(int lo, int hi) {
        this.lo = lo;
        this.hi = hi;
    }

    @Override
    public String toString() {
        return "[" + lo + "," + hi + "]";
    }
}

public class Demo {
    public static ArrayList<Interval> merge(ArrayList<Interval> list) {
        Collections.sort(list, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                if (i1.lo == i2.lo) {
                    return i1.hi - i2.hi;
                }
                return i1.lo - i2.lo;
            }
        });
        System.out.println("Sorted Input: " + list);

        ArrayList<Interval> result = new ArrayList<Interval>();
        Interval prev = list.get(0);
        result.add(prev);
        for (int i = 1; i < list.size(); i++) {
            Interval current = list.get(i);
            if (prev.hi >= current.lo) {
                Interval Interval = new Interval(prev.lo, Math.max(prev.hi, current.hi));
                prev = Interval;
            } else {
                prev = current;
            }
            removeIfExist(result, prev);
            result.add(prev);
        }
        return result;
    }

    private static void removeIfExist(ArrayList<Interval> result, Interval prev) {
        if (result.size() > 0) {
            Interval existing = result.get(result.size() - 1);
            if (existing.lo == prev.lo) {
                result.remove(result.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        ArrayList<Interval> list = new ArrayList<Interval>();
        System.out.println("--------------------------------------------------------------------------------");
        list.add(new Interval(30, 50));
        list.add(new Interval(20, 40));
        list.add(new Interval(75, 90));
        list.add(new Interval(1, 10));
        list.add(new Interval(95, 100));
        list.add(new Interval(65, 80));
        list.add(new Interval(55, 65));
        System.out.println("Input: " + list);
        System.out.println("merged Interval: " + merge(list));
        System.out.println("--------------------------------------------------------------------------------");

    }
}

Answer 3

Use a RangeSet from Guava.

From the documentation:

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

Applied to your example:

public static void main(String args[]) {
    final RangeSet<Integer> ranges = TreeRangeSet.create();
    ranges.add(Range.closed(1, 10));
    ranges.add(Range.closed(20, 40));
    ranges.add(Range.closed(30, 50));
    ranges.add(Range.closed(55, 65));
    ranges.add(Range.closed(65, 80));
    ranges.add(Range.closed(75, 90));
    ranges.add(Range.closed(95, 100));

    System.out.println(ranges);
}

Output:

[[1‥10], [20‥50], [55‥90], [95‥100]]

As Range and TreeRangeSet both implements Serializable you can persist them to Redis as is.