python - 查找 session 重叠

Question

我有任意数量的带有开始和结束时间戳的 session

其中一些 session 重叠。多个 session 可以同时重叠。

我正在尝试找到一种可以检测重叠秒数的算法。 IE 给出了 3 个 session ，例如

-ID-|-start-|-end-|
--1-|-----4-|--10-|
--2-|-----5-|--12-|
--3-|-----8-|--13-|

让它返回一个数字，即 session 重叠的秒数。

我读过interval trees并查看了像 this one 这样的 python 包.

但是，我不确定如何获取给定记录集的重叠秒数。您知道算法或包吗？ Python 是首选，但对其他语言开放，我可以重新实现。

Answer 1

我想到的第一个想法是排序的复杂度为 O(n log n)。如果 starts 和 ends 已经排序，则算法的复杂度为 O(n)。

int findOverlappingTimes(int[] starts, int ends[]) {

    // TODO: Sort starts array
    // TODO: Sort ends array
    // TODO: Assert starts.length == ends.length

    int currStartsIndex = 0;
    int currEndsIndex = 0;

    int currOverlaps = 0;
    int lastOverlapIndex = -1;

    int result = 0;

    while (currEndsIndex < ends.length) {

        if (currStartsIndex < starts.length && starts[currStartsIndex] < ends[currEndsIndex]) {
            if (++currOverlaps == 2) { // Start counting if at least two intervals overlap
                lastOverlapIndex = currStartsIndex;
            }
            currStartsIndex++;
        } else {
            if (--currOverlaps <= 1 && lastOverlapIndex != -1) { // Stop counting
                result += ends[currEndsIndex] - starts[lastOverlapIndex];
                lastOverlapIndex = -1;
            }
            currEndsIndex++;
        }

    }

    return result;
}

输入集的输出

findOverlappingTimes(new int[] { 4, 5, 8 }, new int[] { 10, 12, 13 })

返回7。

该算法背后的基本思想是迭代 session 并计算当前重叠 session 的数量。如果当前时间至少有两个 session 重叠，我们就开始计算重叠时间，如果重叠结束，我们就停止计算重叠时间。

以下是更多测试用例及其各自的输出:

findOverlappingTimes(new int[] { 0 }, new int[] { 0 }) = 0
findOverlappingTimes(new int[] { 10 }, new int[] { 10 }) = 0
findOverlappingTimes(new int[] { 10 }, new int[] { 20 }) = 0
findOverlappingTimes(new int[] { 10, 10 }, new int[] { 10, 10 }) = 0
findOverlappingTimes(new int[] { 10, 10 }, new int[] { 11, 11 }) = 1
findOverlappingTimes(new int[] { 10, 10, 10 }, new int[] { 11, 11, 12 }) = 1
findOverlappingTimes(new int[] { 10, 10, 10, 50, 90, 110 }, new int[] { 11, 12, 12, 100, 150, 160 }) = 52
findOverlappingTimes(new int[] { 4, 5, 8, 100, 200, 200, 300, 300 }, new int[] { 10, 12, 13, 110, 200, 200, 320, 330 }) = 27