计数算法 JavaScript 中范围的重叠

Question

输入整数始终为正数

输入：[[1, 4], [3, 7], [6, 8], [10,15]]
输出：[[1, 8], [10,15]]

输入：[[3, 4], [1,3], [5, 9], [5, 12]]
输出：[[1, 4], [5, 12]]

我读了这个堆栈溢出，但如果有更好的方法，我会徘徊。

Answer 1

对于范围的每个开始和结束，创建一个包含值和+1/-1的开始和结束的对

按值对这些对进行排序，使用 +-1 作为比较函数中的辅助键：(x,+1) before (the same x,-1)

制作ActiveRanges=0，遍历对列表/数组，向ActiveRanges添加+-1。

当ActiveRanges变为非零时，大范围开始。

当ActiveRanges变为零时，大范围结束。

Answer 2

您可以对数据升序进行排序，然后检查前置数据是否适合最后一个范围。如果没有，则将实际数组追加到结果集中。

function groupRanges(array) {
    return array
        .sort(function (a, b) { return a[0]- b[0] || a[1]- b[1]; })
        .reduce(function (r, a) {
            var last = r[r.length - 1] || [];
            if (a[0] <= last[1]) {
                if (last[1] < a[1]) {
                    last[1] = a[1];
                }
                return r;
            }
            return r.concat([a]);
        }, []);
}
console.log(groupRanges([[1, 4], [3, 7], [6, 8], [10,15]]));
console.log(groupRanges([[3, 4], [1,3], [5, 9], [5, 12]]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

这是我想出的，使用 MathJS 库来生成范围：

let input = [[1, 4], [3, 7], [6, 8], [10,15]]
let workArray = input.map( arr => math.range(arr.join(":"), true )._data )
workArray = [].concat.apply([], workArray) // Concatenating all values
workArray = [...new Set(workArray)] // Deduplicating, sorting
let output = [],
	min = workArray[0],
	max = min
for( let i=0, l=workArray.length; i<l ; i++){
	if(max+1 != workArray[i+1]){
		output.push([min,max])
		min = workArray[i+1]
		max=min
	} else {
		max++	
	}
}
console.log(output) // [ [1,8] , [10,15] ]

<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjs/3.13.1/math.min.js"></script>

Answer 4

如果数组的长度为 4(根据您的示例(，并且一切都如您所描述的那样是常量，您可以使用以下简单函数：

function reGroup(arr) {
    const x = [arr[0][0], arr[2][1]];
    return [x, arr[3]];
}