9

有许多起始端对序列。如何找到所有序列中包含的所有范围？start 和 end 是整数，它们可能很远，因此制作序列的位域并对&它们进行 -ing 是不可行的。如果有帮助的话，一个“行”（即一个序列）上的范围（即开始-结束对）不会重叠。开始和结束有上下限，我认为 32 位整数就足够了（即 0 <= values <= 65535）。

让我举个例子：

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

结果应该是：

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

上面的例子大概是：

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

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

4

3 回答 3

8

假设每个序列中的范围不重叠，这应该不难。在这种情况下，只需遍历所有点并跟踪您何时进入或离开范围。

将所有序列中的所有点放入一个列表中，对其进行排序并记住每个点是起点还是终点。

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

当计数器等于序列数（在您的示例中为三个）时，您已找到一个范围的开始，下一个点是该范围的结束。

请注意，如果每个序列中的范围按 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
于 2013-01-10T18:24:52.177 回答
5

我认为您可以简单地通过将序列 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
于 2013-01-10T18:15:25.133 回答
0

它被称为最长公共子串。我可以使用后缀树来解决。这个博客上有一个非常干净的 Java 实现，它不仅可以使用两个源字符串。

我不知道你是否在处理角色，但我相信如果你不这样做，你可能会适应它。

于 2013-01-10T17:53:15.200 回答