主页 / 问题 / 977859
Accepted
Андрей NOP
Asked:2020-05-04 18:21:03 +0000 UTC2020-05-04 18:21:03 +0000 UTC

合并段

  • 772

在输入有一些（连续）轴（数字或时间，没关系）的段列表，每个段由一对（有序）坐标表示 - 开始和结束（这些点也属于部分）。

有必要合并所有相交的线段并在输出处获得一个没有交点的线段列表（但这个新列表不应包含不在输入线段中的点）。

例如，我们在输入处有：

[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³) 复杂性。
有没有可能写出更好的解决方案？

有一个思路：对输入列表进行排序，并以某种方式适配扫描线方式；但我仍然无法弄清楚如何实现它。

алгоритм

4 个回答

  1. Best Answer

    按左点排序是正确的第一步，我们得到：

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

    接下来，我们将第一段与第二段进行比较——第二段的开头落入第一段，这意味着我们合并了段：开头将是第一段的开头，结尾将是最大的（首先，第二个结束），我们得到[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))

    • 10

  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));

    • 2

  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<int[]>();

        var curr = intervals[0];

        for(int i=1; i<intervals.Length; i++)
        {           
            var next = intervals[i];                
            if (curr[1] >= 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<int[]>
    {
        public int Compare(int[] x, int[] y)
        {
            return x[0].CompareTo(y[0]);
        }
    }
}

    这段代码击败了 99.7% 的leetcode解决方案（C# 解决方案）

    • 1 

  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 }
]))

    • 0

相关问题