重叠序列

Question

有许多起始端对的序列.如何找到所有序列中包含的所有范围？开始和结束是整数,它们可能很远,因此制作序列的位域并且&它们是不可行的.如果有帮助,一个"行"(即一个序列)上的范围(即起始端对)不重叠.并且开始和结束都有下限和上限,我认为32位整数就足够了(即0 <=值<= 65535).

让我举一个例子:

|----------|       |---------------------|           |----------|
     |----------------------|                      |-------|
                |---------------------|                 |--|

结果应该是:

                   |--------|                           |--|

上面的例子大致如下:

row1 = (100, 200), (300, 600), (800, 900)
row2 = (140, 450), (780, 860)
row3 = (280, 580), (820, 860)
result = (300, 450), (820, 860)

另外,有没有任何已知的算法？我的意思是,这个问题有名字吗？

Answer 1

假设每个序列中的范围不重叠,那应该不是很难.在这种情况下,只需迭代所有点并在进入或离开范围时进行跟踪.

将所有序列中的所有点都放入一个列表中,对其进行排序并记住每个点是否为起点或终点.

100 S ---
140 S  |   ---
200 E ---   |
280 S       |  ---
300 S ---   |   |
450 E  |   ---  |
580 E  |       ---
600 E ---
780 S      ---
800 S ---   |
820 S  |    |  ---
860 E  |   ---  |
860 E  |       ---
900 E ---

现在你遍历这个列表,每次你遇到一个起点你都会增加一个计数器,每当你遇到一个终点时你就减少了计数器.

      0
100 S 1
140 S 2
200 E 1
280 S 2  
300 S 3 <--
450 E 2 <--
580 E 1
600 E 0
780 S 1
800 S 2
820 S 3 <--
860 E 2 <--
860 E 1
900 E 0

当计数器等于序列数 - 在您的示例中为3时 - 您已找到一个范围的开头,下一个点是该范围的结束.

请注意,如果每个序列中的范围按start排序或者可以按start排序,则甚至不需要显式构建列表.在这种情况下,您可以通过保持指向每个序列中当前范围的指针来并行迭代所有序列.

这里是C#中的全部内容 - 范围类.

internal sealed class Range
{
    private readonly Int32 start = 0;

    private readonly Int32 end = 0;

    public Range(Int32 start, Int32 end)
    {
        this.start = start;
        this.end = end;
    }

    internal Int32 Start
    {
        get { return this.start; }
    }

    internal Int32 End
    {
        get { return this.end; }
    }
}

具有标志的点的类,用于区分起点和终点.

internal sealed class Point
{
    private readonly Int32 position = 0;

    private readonly Boolean isStartPoint = false;

    public Point(Int32 position, Boolean isStartPoint)
    {
        this.position = position;
        this.isStartPoint = isStartPoint;
    }

    internal Int32 Position
    {
        get { return this.position; }
    }

    internal Boolean IsStartPoint
    {
        get { return this.isStartPoint; }
    }
}

最后是算法和测试程序.

internal static class Program
{
    private static void Main()
    {
        var s1 = new List<Range> { new Range(100, 200), new Range(300, 600), new Range(800, 900) };
        var s2 = new List<Range> { new Range(140, 450), new Range(780, 860) };
        var s3 = new List<Range> { new Range(280, 580), new Range(820, 860) };

        var sequences = new List<List<Range>> { s1, s2, s3 };

        var startPoints = sequences.SelectMany(sequence => sequence)
                                   .Select(range => new Point(range.Start, true));

        var endPoints   = sequences.SelectMany(sequence => sequence)
                                   .Select(range =>  new Point(range.End, false));

        var points = startPoints.Concat(endPoints).OrderBy(point => point.Position);

        var counter = 0;

        foreach (var point in points)
        {
            if (point.IsStartPoint)
            {
                counter++;

                if (counter == sequences.Count)
                {
                    Console.WriteLine("Start {0}", point.Position);
                }
            }
            else
            {
                if (counter == sequences.Count)
                {
                    Console.WriteLine("End   {0}", point.Position);
                    Console.WriteLine();
                }

                counter--;
            }
        }

        Console.ReadLine();
    }
}

输出如下所示.

Start 300
End   450

Start 820
End   860

Answer 2

我认为你可以通过将2到2的序列融合来做到这一点.

每个融合应该在所考虑的序列中的间隔数的线性时间内是可行的(如果序列被分类),并且需要M-1融合(具有M个序列)

举个例子并添加一个额外的序列:

|----------|       |---------------------|           |----------|
     |----------------------|                      |-------|
                |---------------------|                 |--|
        |-----------------------------------|           |-----|  

保险丝按顺序排列:

     |-----|       |--------|                        |-----|
                |---------------------|                 |--|

保险丝:

                   |--------|                           |--|

但是你可以找到一种更快的方法来做到这一点.最坏的情况是O(N log M)运行时间(N个总间隔数).

编辑:用于融合的伪代码

Take s1 and s2 an iterator on each sequence
While there are still intervals in both sequences
    Compare the intervals:
    If s1.begin < s2.begin
        If s2.begin < s1.end
            If s2.end > s1.end
                Add [s2.begin,s1.end] to the fused sequence
                Increment s1
            Else
                Add [s2.begin,s2.end] to the fused sequence
                Increment s2
        Else
            Increment s1
    Else
        Same thing with s1 and s2 reversed