Отличия Ranges

Question

Если у меня есть следующие массивы, с каждым элементом, представляющих пары целочисленных диапазонами:

var a = [[0, 47], [50, 51], [53, 53], [55, 55], [58, 97], [101, 101], [103, 1114111]]; 
var b = [[48, 57], [97, 102]]; 

Я использую this code, чтобы вычислить пересечение:

var output = []; 

for (var i = 0; i < a.length; ++i) { 
    for (var j = 0; j < b.length; ++j) { 
     var intersection = [ 
     Math.max(a[i][0], b[j][0]), 
     Math.min(a[i][1], b[j][1]), ]; 

     if (intersection[0] <= intersection[1]) { 
      output.push(intersection) 
     } 
    } 
} 

console.log(JSON.stringify(output)); 

[ [ 50, 51 ], [ 53, 53 ], [ 55, 55 ], [ 97, 97 ], [ 101, 101 ] ] 

Я также необходимо, чтобы вычислил разницу (все значения 0..1114111, за исключением диапазонов, которые пересекаются выше).

Что такое эффективный способ сделать это?

Answer 1

Наблюдение: «все значения 0..1114111, за исключением диапазонов, которые пересекаются выше», фактически тривиальны, вы просто перебираете пересечение и выводите его дополнение (соединяйте конечные точки с начальными точками следующих интервалов).

Таким образом, ваша проблема сводится к поиску пересечения быстрее. Используйте алгоритм развертка строки:

1. Создать список событий (t, x, y) где t является пограничной точкой интервала и x является 1, если интервал пришел из a и 2, если он пришел из b. y - 1, если граничная точка является начальной точкой или -1, если она является конечной точкой.
2. Сортировать лексикографически (t, -y)
3. Набор count[1] = count[2] = 0
4. перебирать точки событий. Обновление count[x] += y.

Теперь результатом являются диапазоны, в которых count[1] > 0 и count[2] > 0 в то же время.

Сложность O(n log n). Вот пример кода: http://jsfiddle.net/QA5FY/14/ Благодаря пользователю Xotic750 для обеспечения базовой реализации.

Javascript

var a = [ 
    [0, 47], 
    [50, 51], 
    [53, 53], 
    [55, 55], 
    [58, 97], 
    [101, 101], 
    [103, 1114111] 
]; 

var b = [ 
    [48, 57], 
    [97, 102] 
]; 

var evts = []; 

function add(arr, x) { 
    arr.forEach(function (pair) { 
     evts.push({ 
      t: pair[0], 
      x: x, 
      y: 1 
     }, { 
      t: pair[1], 
      x: x, 
      y: -1 
     }); 
    }); 
} 

add(a, 0); 
add(b, 1); 

evts.sort(function (a, b) { 
    return (a.t != b.t) ? (a.t - b.t) : (b.y - a.y); 
}); 

var last = -1; 
var count = [0, 0]; 
var res = []; 

for (var i = 0; i < evts.length; ++i) { 
    count[evts[i].x] += evts[i].y; 
    if (count[evts[i].x] === 1 && count[evts[i].x^1] > 0) last = i; 
    else if (count[0] === 0 || count[1] === 0) { 
     if (last >= 0) res.push([evts[last].t, evts[i].t]); 
     last = -1; 
    } 
} 

res.forEach(function (pair) { 
    console.log(pair[0] + " " + pair[1]); 
}); 

Выход

50 51 
53 53 
55 55 
97 97 
101 101