algorithm - 重叠序列

Question

有许多开始-结束对序列。如何找到所有序列中包含的所有范围？开始和结束是整数，它们可能相距很远，因此制作序列的位域和 &-ing 它们是不可行的。一个“行”(即一个序列)上的范围(即开始-结束对)不重叠，如果有帮助的话。开始和结束有下限和上限，我认为 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

当计数器等于序列数时(在您的示例中为三个)，您已找到一个范围的起点，下一点是该范围的终点。

请注意，如果每个序列中的范围按开始排序或可以按开始排序，则甚至不需要显式构建列表。在这种情况下，您可以通过在每个序列中保留指向当前范围的指针来并行遍历所有序列。

这里是 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