在O(n)中组合不同的数字范围

Question

我目前正在跟踪视频的用户播放时间,我正在尝试确定用户观看的视频的百分比.我已经将问题推广到给定一系列可能重叠的数字范围,如何将它们组合成一系列非重叠的数字范围(即转换为"0-10,5-15,30-45,20-25")进入"0-15,20-25,30-45".

我有一个相对冗长的解决方案,前提是如果对数字范围进行排序,那么组合两个相邻的数字范围相对微不足道(如果它们重叠或者它们保持分离,则将它们组合起来).因此,我们首先对数字范围进行排序,然后遍历范围并组合它们.

由于排序是最坏的情况O(nlgn),这意味着我的解决方案应该是O(nlgn),我想知道是否有人知道O(n)问题的解决方案？

http://jsfiddle.net/457PH/2

var testcase = [
        [0, 30], [40, 50], [5, 15], [70, 95], [45, 75], [0, 10],
        [110, 115], [115, 120], [140, 175], [125, 160]
    ];

//sorts the array in ascending order (based on first element)
//if the first elements are the same, order based on second element (prioritising elements that are bigger)
testcase.sort(function(a, b) {
    if (a[0] !== b[0]) return a[0] - b[0];

    return b[1] - a[1]
})


function evaluate(a, b) {
    var result = [];
    //tests that the array is sorted properly
    if ((a[0] > b[0]) || ((a[0] === b[0] ) && (a[1] < b[1]))) throw new Error('Array not sorted properly');

    //if a and b do not overlap, then push both in the result
    if(b[0] > a[1]) {
        result.push(a, b);
    }
    //if a and b overlap
    else {
        var newElement = [a[0], Math.max(a[1], b[1])];
        result.push(newElement);
    }
    return result;
}

console.log(testcase)
var combinedArr = [testcase[0]];
for (var i = 1; i < testcase.length; i++) {
    var popped = combinedArr.pop();
    combinedArr = combinedArr.concat(evaluate(popped, testcase[i]));
}
console.log(combinedArr);

Answer 1

一种替代的解决方案,O(W+n*|S|)其中,|S|为每一个间隔的平均尺寸和W在列表中的最大值将被使用一个bitset,和迭代的每个元素,并设置所有相关位.
在另一次迭代中 - 打印位集中的所有间隔(已排序).

所以,这种方法的算法基本上是:

1. 创建一个大小为W的位集,只有在某个区间内才设置一个位.
2. 迭代bitset并打印间隔 - 现在这很容易.

虽然这在渐近复杂度方面可能要差得多- 如果W或者|S|很大 - 注意这里的常量相当小,因为位操作相当容易实现.

选择哪个实际上更好应该使用经验基准并实现统计显着性.

伪代码:

//create the bitset:
b <- new bitset
for each interval [x1,x2]:
  for each element i from x1 to x2:
     b[i] = 1

//print intervals:
first <- -1
for each element i from 0 to W+1: //regard b[W] as 0
  if b[i] == 0 and first != -1:
     print (first,i-1)
     first = -1
  else if b[i] == 1 and first == -1:
     first = i