нисходящие диапазоны сливаются? - PullRequest
Новая
       6

нисходящие диапазоны сливаются?

4 голосов
/ 25 февраля 2012

Я хочу объединить несколько интервалов следующим образом: 

>>> ranges = [(30, 45), (40, 50), (10, 50), (60, 90), (90, 100)]
>>> merge(ranges)
[(10, 50), (60, 100)]

Я не в поле cs.Я знаю, как сделать это путем итерации, но задаюсь вопросом, существует ли более эффективный подход «сверху вниз» для их более эффективного объединения, возможно, с использованием какой-то специальной структуры данных?

Спасибо.

Ответы [ 3 ]

3 голосов
/ 25 февраля 2012

Дерево интервалов определенно работает, но оно сложнее, чем вам нужно. Дерево интервалов - это «онлайн» решение, поэтому оно позволяет добавлять некоторые интервалы, просматривать объединение, добавлять дополнительные интервалы, снова просматривать и т. Д.

Если у вас есть все интервалы заранее, вы можете сделать что-то попроще:

  1. Начните с ввода

    диапазоны = [(30, 45), (40, 50), (10, 50)]

  2. Преобразование списка диапазонов в список конечных точек. Если у вас есть диапазон (A, B), вы преобразуете его в две конечные точки: (A, 0) будет левой конечной точкой и (B, 1) будет правой конечной точкой.

    конечные точки = [(30, 0), (45, 1), (40, 0), (50, 1), (10, 0), (50, 1)]

  3. Сортировка конечных точек

    конечные точки = [(10, 0), (30, 0), (40, 0), (45, 1), (50, 1), (50, 1)]

  4. Сканирование вперед по списку конечных точек. Увеличивайте счетчик, когда видите левую конечную точку, и уменьшайте счетчик, когда видите правую конечную точку. Всякий раз, когда счетчик достигает 0, вы закрываете текущий интервал слияния.

Это решение может быть реализовано в несколько строк.

2 голосов
/ 25 февраля 2012

Да, эффективный способ сделать это - использовать интервальное дерево .

0 голосов
/ 21 февраля 2017

Следующий алгоритм в C # делает то, что вы хотите.Он использует интервалы DateTime, но вы можете адаптировать его так, как вам нравится.Как только коллекция отсортирована в порядке возрастания начала, если начало следующего интервала находится в конце предыдущего интервала или перед ним, они перекрываются, и вы продлеваете время окончания наружу, если это необходимо.В противном случае они не перекрываются, и вы сохраняете предыдущий результат.

public static List<DateTimeRange> MergeTimeRanges(List<DateTimeRange> inputRanges)
{
  List<DateTimeRange> mergedRanges = new List<DateTimeRange>();

  // Sort in ascending start order.
  inputRanges.Sort();

  DateTime currentStart = inputRanges[0].Start;
  DateTime currentEnd = inputRanges[0].End;

  for (int i = 1; i < inputRanges.Count; i++)
  {
    if (inputRanges[i].Start <= currentEnd)
    {
      if (inputRanges[i].End > currentEnd)
      {
        currentEnd = inputRanges[i].End; // Extend range.
      }
    }
    else
    {
      // Save current range to output.
      mergedRanges.Add(new DateTimeRange(currentStart, currentEnd));

      currentStart = inputRanges[i].Start;
      currentEnd = inputRanges[i].End;
    }
  }

  mergedRanges.Add(new DateTimeRange(currentStart, currentEnd));

  return mergedRanges;
}
...