Алгоритм: Объединить перекрывающиеся сегменты

Question

Я следующий ADT (не отсортированный): List<Segment>

//direction is from 0 to 2pi 
class Segment { 
    int start; 
    int end; 
} 

Они представляющие, например, такую ​​ситуацию:

Как сделать фазу слияния (зеленая стрелка в примере)? Очевидно, мне нужно перебирать список и каждый сегмент по сравнению со всеми остальными сегментами, а для каждой пары, если возможно, сделать простой слияние (это легко). Но затем на второй итерации мне нужно как-то вернуться к началу списка и начать все заново и т. Д. Поэтому я изо всех сил пытаюсь найти способ сближения этого алгоритма.

EDIT: Сегменты могут быть circular- От 1.75pi к 0.5pi и т.д ...

Answer 1

Сортировка сегментов по времени начала.

Создайте стек, который будет хранить объединенные интервалы.

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

Если время начала больше, чем время окончания элемент в верхней части стека, добавьте интервал в стек.

Если время начала меньше времени окончания элемента в верхней части стека, обновите время окончания элемента в верхней части стека, чтобы оно соответствовало времени окончания нового элемента.

Когда весь массив обрабатывается, полученный стек должен содержать объединенные интервалы.

Реализация на Java:

/** 
* Definition for an interval. 
* public class Interval { 
*  int start; 
*  int end; 
*  Interval() { start = 0; end = 0; } 
*  Interval(int s, int e) { start = s; end = e; } 
* } 
*/ 
public class Solution { 
    public List<Interval> merge(List<Interval> intervals) { 
     Deque<Interval> stack = new ArrayDeque<Interval>(); 

     Collections.sort(intervals, new Comparator<Interval>() { 
       public int compare(Interval p1, Interval p2) { 
        return Integer.compare(p1.start, p2.start); 
       } 
      } 
     ); 

     if (intervals.size() < 1) { 
      return intervals; 
     } 
     stack.push(intervals.get(0)); 

     for (int j = 1; j < intervals.size(); j++) { 
      Interval i = intervals.get(j); 
      Interval top = stack.peek(); 
      if (top.end < i. start) { 
       stack.push(i); 
      } 
      else if (top.end < i.end) { 
       top.end = i.end; 
      } 
     } 
     return new ArrayList<Interval>(stack); 

    } 
} 

Answer 2

Сортировать ваши сегменты по начальной точке.

Затем для каждого сегмента, если его начальная точка находится между начальной и конечной точкой предыдущего сегмента, а ее конечная точка больше конечной точки предыдущего сегмента, установите конечную точку предыдущего сегмента на конечную точку этого сегмента и удалить/игнорировать текущий сегмент.

Если текущий сегмент полностью включен в предыдущий сегмент, просто удалите его/проигнорируйте.

Это O(n log n) из-за сортировки, и вам не нужно сравнивать каждый сегмент со всеми остальными сегментами.

Будьте осторожны, как вы делаете удаление или игнорирование. Это должно быть операция O(1). Например, сохраните переменную, которая всегда хранит предыдущий не удаленный сегмент и, возможно, некоторый флаг для удаленных сегментов, чтобы вы знали, какие из них собирать в конце. .remove() операции с коллекциями может быть O(n), и вы хотите этого избежать.

Answer 3

Поместите все конечные точки в одном массиве и присвоить им полярность (+ затем -). Затем отсортируйте список.

По мере прохождения списка по возрастанию значения достаточно обновить счетчик перекрывающихся сегментов.

0+ 0.75- 0.5+ 1- 1.25+ 2- 

затем сортируют,

0+ 0.5+ 0.75- 1- 1.25+ 2- 

дает отсчеты (инициализированы на 0)

1 2 1 0 1 0 

, следовательно, пределы интервала (на переходах 0 to >0 или >0 to 0)

0 1 1.25 2 

---

Это также может быть сделано исключительно на месте, без дополнительных флагов.

Вы сортируете start и end значения отдельно, на месте (не перемещайте Segments в целом); таким образом, полярности остаются неявными.

Затем перемещайте список в виде слияния двух отсортированных списков (используя два независимых индекса) и сохраняйте счетчик перекрытия. Вы можете переписать границы на месте, так как результат слияния не имеет больше интервалов.

Начиная с

[0 0.75][0.5 1][1.25 2] 

оба списка случайно уже отсортирован.

0 0.5 1.25 (+) 
0.75 1 2 (-) 

Перейдем к слиянию, которые будут выбирать элементы в порядке

+ + - - + - 

и получают конечный результат посредством сдвига значений

[0 1][1.25 2][x x] 

---

В случае связей на границах, лучше обработать + и - в таком порядке, чтобы y ou избегать испускания двух равных границ.

Answer 4

Я добавлю к другим ответам подход к округлости, то есть что вы должны делать, если у вас есть сегменты, переходящие по 2pi.

Есть два способа справиться с этим. Один из них состоит в том, чтобы просто разбить каждый такой сегмент на два: один идет от места до 2pi, а другой - от нуля до места. После этого разрешите проблему, как если бы она не была круговой, а затем, если у вас есть сегмент, начинающийся с нуля, и сегмент, заканчивающийся на 2pi, затем просто слейте их.

Второй подход специально для ответа Ив Дауста. Там вам нужно только знать, сколько сегментов покрывает нулевую точку (вы можете легко вычислить это); после этого вы инициализируете «счет» не с нулем, а с таким количеством сегментов покрытия.