Разделение множества перекрывающихся диапазонов на множество непересекающихся

У меня есть массив перекрывающихся диапазонов:

var ranges = [{
    "from": 0,
    "to": 100
}, {
    "from": 50,
    "to": 200
}, {
    "from": 0,
    "to": 100
}, {
    "from": 70,
    "to": 200
}, {
    "from": 90,
    "to": 300
}];

Мне нужно преобразовать его в набор непересекающихся диапазонов, т.е. э.:

var nonOverlapping = splitRanges(ranges);

/*
nonOverlapping = [{
    "from": 0,
    "to": 49
}, {
    "from": 50,
    "to": 69
}, {
    "from": 70,
    "to": 89
}, {
    "from": 90,
    "to": 100
}, {
    "from": 101,
    "to": 200
}, {
    "from": 201,
    "to": 300
}]
*/

Я сделал функцию, которая делает это (в JavaScript), но, конечно, как вы можете видеть, она работает очень медленно, потому что использует так называемый «наивный подход»:

function splitRanges(ranges) {
    var repeat, length, i, j;
    var rangeA, rangeB, intersection;
    do {
        repeat = false;
        length = ranges.length;
        for (i = 0; i < length; i++) {
            rangeA = ranges[i];
            for (j = i + 1; j < length; j++) {
                rangeB = ranges[j];
                if (isIntersectingRanges(rangeA, rangeB)) {
                    repeat = true;
                    ranges.splice(i, 1);
                    intersection = splitRange(rangeA, rangeB);
                    while (intersection.length) {
                        ranges.push(intersection.shift());
                    }
                }
                if (repeat) break;
            }
            if (repeat) break;
        }
    } while (repeat);
}

Может ли кто-нибудь помочь мне переписать это, чтобы оно вело себя так же и делало это быстрее, чем наивный подход?

ИЗМЕНИТЬ:

Алгоритм должен иметь возможность отслеживать идентификаторы диапазонов + правильно обрабатывать диапазоны, где от == до:

var ranges = [{
    id: 1,
    from: 0,
    to: 100
}, {
    id: 2,
    from: 30,
    to: 30,
}, {
    id: 3,
    from: 0,
    to: 100
}, {
    id: 4,
    from: 90,
    to: 300
}];

Ожидаемый результат:

[{
    "id": 3,
    "from": 90,
    "to": 100
}, {
    "id": 4,
    "from": 90,
    "to": 100
}, {
    "id": 4,
    "from": 101,
    "to": 300
}, {
    "id": 1,
    "from": 0,
    "to": 29
}, {
    "id": 1,
    "from": 90,
    "to": 100
}, {
    "id": 3,
    "from": 0,
    "to": 29
}, {
    "id": 1,
    "from": 30,
    "to": 30
}, {
    "id": 1,
    "from": 31,
    "to": 89
}, {
    "id": 2,
    "from": 30,
    "to": 30
}, {
    "id": 3,
    "from": 30,
    "to": 30
}, {
    "id": 3,
    "from": 31,
    "to": 89
}]

javascript set range intervals overlapping
person Ruslan    schedule 19.05.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Это дает требуемые результаты для указанного ввода:

function splitRanges (intervals) { 'use strict';
  // Create arrays of the from and to values, do not record duplicate values 
  for (var to = [], from = [], n, i = intervals.length; i--;) {
    if (to.indexOf (n = intervals[i].to) < 0)
      to.push (n);
    if (from.indexOf (n = intervals[i].from) < 0)
      from.push (n);
  }

  // Sort both arrays
  to.sort (function (a, b) { return a-b; });
  from.sort (function (a, b) { return a-b; });

  // Create new intervals array
  intervals = [];
  while (to.length)
    intervals.push ({
      from: from.shift (),
      to: from.length == 0 ? (from.push ((n = to.shift ()) + 1), n) :
          from[0] > to[0] ? from[1] - 1 : from[0] - 1
    });

  return intervals;
}

Когда одно и то же число появляется как значение от и до, создается «ложный» нулевой диапазон. Не знаю, может ли этот случай произойти в ваших данных или лишний диапазон является проблемой

person HBP    schedule 19.05.2012
comment
В этом проблема, потому что алгоритм должен уметь обрабатывать диапазоны, где (от === до) - person Ruslan; 21.05.2012
comment
Можете ли вы добавить к своему примеру 1) нулевой интервал от 60 до 60 и 2) другой диапазон от 200 до 230 и обновить ожидаемые результаты. - person HBP; 21.05.2012
comment
Да, пожалуйста, посмотрите на последний раздел исходного вопроса, я разместил пример ниже редактирования, есть диапазон 30..30, и ожидаемый результат, полученный моим неоптимальным решением. - person Ruslan; 21.05.2012
comment
Я сделал страницу jsFiddle, которая содержит пару функций, которые я использовал для разделения. Просто пропустите массив диапазонов (как в описании моего вопроса) в текстовую область и нажмите «Разделить»! кнопка, вторая текстовая область будет содержать результат разделения. Так что это именно то, что мне нужно и как мне нужно, чтобы это работало, только быстрее. Надеюсь, это поможет: jsfiddle.net/tbtXz - person Ruslan; 21.05.2012
comment
Любая оптимизированная версия этого.? - person Stanly; 12.03.2018