сверху вниз слияния?

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

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

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

Спасибо.

4 голоса | спросил Jingping 25 FebruaryEurope/MoscowbSat, 25 Feb 2012 00:29:01 +0400000000amSat, 25 Feb 2012 00:29:01 +040012 2012, 00:29:01

3 ответа


0

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

ответил jason 25 FebruaryEurope/MoscowbSat, 25 Feb 2012 00:31:26 +0400000000amSat, 25 Feb 2012 00:31:26 +040012 2012, 00:31:26
0

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

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

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

    range = [(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, вы закрываете текущий интервал слияния.

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

ответил Igor ostrovsky 25 FebruaryEurope/MoscowbSat, 25 Feb 2012 01:39:28 +0400000000amSat, 25 Feb 2012 01:39:28 +040012 2012, 01:39:28
0

Следующий алгоритм в 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;
}
ответил Pete Rihaczek 21 FebruaryEurope/MoscowbTue, 21 Feb 2017 01:00:48 +0300000000amTue, 21 Feb 2017 01:00:48 +030017 2017, 01:00:48

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132