Слияние отрезков

#алгоритм #любой_язык

На входе есть список отрезков какой-то (непрерывной) оси (числовой или временной,
не важно), каждый отрезок представлен парой (упорядоченных) координат — начало и конец
(эти точки также принадлежат отрезку).

Необходимо слить все пересекающиеся отрезки и получить на выходе список отрезков
не имеющих пересечений (но этот новый список не должен иметь точки, которых не было
в отрезках на входе).

Например, имеем на входе:

[1; 5]
[2; 4]
[7; 9]
[3; 6]


тогда, на выходе необходимо получить:

[1; 6] // здесь слиты [1; 5], [2; 4], [3; 6]
[7; 9]


реализовал алгоритм примерно такой:



function merge(segments) {
  while (true) {
    const newSegments = [];
    for (const x of segments) {
      let found = false;
      for (const y of newSegments) {
        if (x.end >= y.start && x.start <= y.end) {
          y.start = Math.min(y.start, x.start);
          y.end = Math.max(y.end, x.end);
          found = true;
          break;
        }
      }
      if (!found) newSegments.push(x);
    }
    if (segments.length == newSegments.length) break;
    segments = newSegments;
  }
  return segments;
}

function print(segments) {
  console.log(segments.map(s => `[${s.start}; ${s.end}]`).join(' '));
}

let segments = [
  { start: 1, end: 5 },
  { start: 2, end: 4 },
  { start: 7, end: 9 },
  { start: 3, end: 6 }
];

print(segments);
print(merge(segments));




Он работает, но имеет сложность O(n³).
Можно ли написать решение лучше?

Есть идея: отсортировать входной список и как-то адаптировать метод сканирующей прямой;
но как это реализовать пока не могу придумать.
    

Ответы

Ответ 1

Сортировка по левой точке - это правильный первый шаг, получаем:

[1; 5]
[2; 4]
[3; 6]
[7; 9]


Далее сравниваем первый отрезок со вторым - начало второго попадает в первый отрезок,
значит сливаем отрезки: началом будет начало первого, а концом - max(конец первого,
конец второго), получаем [1; 5].

[1; 5]
[3; 6]
[7; 9]


Так же сливаем [1; 5] и [3; 6] в [1; 6]

[1; 6]
[7; 9]


[1; 6] и [7; 9] не пересекаются, значит фиксируем [1; 6] с ним уже никакой другой
отрезок не пересечется, и повторяем все действия начиная с [7; 9]

сложность сортировки O(n log(n)), сложность слияния O(n) итого O(n log(n))


Ответ 2

Получилось в итоге так:



function merge(segments) {
  if (segments.length === 0) return [];
  const inp = segments.map(s => ({...s}));
  inp.sort((a, b) => a.start - b.start);
  const out = [];
  let s = inp[0];
  for (let i = 1; i < inp.length; ++i) {
    if (inp[i].start <= s.end) {
      s.end = Math.max(s.end, inp[i].end);
    } else {
      out.push(s);
      s = inp[i];
    }
  }
  out.push(s);
  return out;
}

function print(segments) {
  console.log(segments.map(s => `[${s.start}; ${s.end}]`).join(' '));
}

let segments = [
  { start: 1, end: 5 },
  { start: 2, end: 4 },
  { start: 7, end: 9 },
  { start: 3, end: 6 }
];

print(segments);
print(merge(segments));


Ответ 3

больше от скуки запилил решение на C#

public class Solution
{
    public int[][] Merge(int[][] intervals)
    {
        if (intervals == null || intervals.Length == 0) return new int[0][];

        Array.Sort(intervals, 0, intervals.Length, new IntervalComparer());
        var stack = new Stack();

        var curr = intervals[0];

        for(int i=1; i= next[0])                         
                curr = new int[] {curr[0], Math.Max(curr[1], next[1])};
            else 
            {
                stack.Push(curr);
                curr = next;                    
            }
        }           
        stack.Push(curr);

        var ret = new int[stack.Count][];
        for(int i = ret.Length-1; i>=0; i--)
            ret[i] = stack.Pop();

        return ret;
    }

    private class IntervalComparer : IComparer
    {
        public int Compare(int[] x, int[] y)
        {
            return x[0].CompareTo(y[0]);
        }
    }
}


Этот код побил 99.7% решений этой задачи на leetcode (решений на C#)


Ответ 4

const merge = ss => {
  ss = ss.sort((a, b) => a.start - b.start)
  let c = ss.shift()
  const m = [c]
  ss.forEach(s => (s.start <= c.end) ? (s.end > c.end) && (c.end = s.end) : m.push(c
= s))
  return m
}

console.log(merge([
  { start: 1, end: 5 },
  { start: 2, end: 4 },
  { start: 7, end: 9 },
  { start: 3, end: 6 }
]))