Javascript array of ranges reduction

问题:

What is the best possible way to reduce an array of ranges in javascript.

For example I have

1-3,4-5,10-12,2-4

the result I need for this is

1-5, 10-12

What is the best way to tackle this problem ?

回答1:

I would first create another array with no duplicates, storing the numbers that are covered by the ranges:

1-3   covers 1, 2, 3    --> [1, 2, 3]
4-5   covers 4, 5       --> [1, 2, 3, 4, 5]
10-12 covers 10, 11, 12 --> [1, 2, 3, 4, 5, 10, 11, 12]
2-4   covers 2, 3, 4    --> [1, 2, 3, 4, 5, 10, 11, 12]

Then, sort the array:

[1, 2, 3, 4, 5, 10, 11, 12] // nothing changed in this example

Finally, rebuild the ranges, depending on the consecutive values:

1-5
10-12

回答2:

1) parse the input to build a structure like this:

var rlist = [
    {min: 1, max: 3},
    {min: 4, max: 5},
    {min: 10, max: 12}
    {min: 2, max: 4}
];

2) marge each interval of that list into a new list:

var olist = [], i, j, r, p, s;
for (i = 0; i < rlist.length; ++i) {
    r = rlist[i];
    for (j = 0; j < olist.length; ) {
        p = olist[j];
        if (r.max+1 < p.min) {
            // insert here
            break;
        } else if (p.max+1 >= r.min) {
            // intersection
            olist.splice(j, 1);
            r.min = p.min;
            r.max = Math.max(r.max, p.max);
        } else {
            ++j;
        }
    }
    olist.splice(j, 0, r);
}

3) Convert result into a string

s = "";
for (j = 0; j < olist.length; ++j) {
    if (j > 0) {
        s += ",";
    }
    s += olist[j].min + "-" + olist[j].max;
}

Fiddle