algorithm - 如何确定范围列表是否涵盖给定范围？

Question

我想有效地确定范围列表是否涵盖给定范围。例如范围列表 [(0-3), (3-5), (4-8), (6-10)] 涵盖范围 (0-10) 而 [(5-10), (0- 3)] 没有。该列表可以包含重叠部分并且不一定是有序的。

我尝试实现如下所示的 Continuous 函数，该函数检查字节范围的 slice 是否包含传递给定的 start 和 end范围。

type byteRange struct {
    start int64
    end   int64
}

type byteRanges []*byteRange

func (brs byteRanges) Len() int {
    return len(brs)
}

func (brs byteRanges) Swap(i, j int) {
    brs[i], brs[j] = brs[j], brs[i]
}

func (brs byteRanges) Less(i, j int) bool {
    return brs[i].start < brs[j].start
}

func (brs byteRanges) Continuous(start int64, end int64) bool {
    curPos := start
    sort.Sort(brs)

    for _, br := range brs {
        if br.start > curPos+1 {
            return false
        }

        if curPos < br.end {
            curPos = br.end
        }

        if curPos >= end {
            return true
        }
    }

    return false
}

该函数运行正常，但在处理大量范围列表以及经常调用时性能不佳。有人可以推荐可以加速此逻辑的算法/实现吗？

Answer 1

因为你会反复调用Continuous在同一组范围内，创建 Condense 是个好主意方法(或任何你想调用它的方法)，它将获取一个 slice 并返回一个新的 slice ，其中的范围已排序并合并了任何重叠的范围。您只需要调用Condense 一次 用于任何给定的一组范围。 Continuous然后可以要求它只在 Condense 的结果上调用. (为了强制执行此要求，最好让 Condense 实际上返回一个自定义类型的 struct，它只是一个 slice 的包装器，并且只在该 Continuous 类型上定义 struct。如果你想要 - 为了方便起见 - 然后你可以定义一个单独的 Continuous 方法，可以 直接在 slice 上调用，它调用 Condense 然后是 Continuous 。那个方便的方法会再次变慢，当然，但对于只检查一次的集合可能会很方便。)

Condense 中的合并逻辑非常简单:

• 如果 slice 为空，则返回它(提前退出)。
• 按 start 对范围进行排序.
• 创建一个名为 result 的新 slice .
• 初始化prevRange到第一个范围。
• 遍历范围。每一个人:
  • 如果当前范围在prevRange.end + 1之后开始, 添加 prevRange至 result , 然后设置 prevRange到当前范围。
  • 否则，如果当前范围在prevRange.end之后结束, 设置 prevRange.end到 end当前范围的。
• 添加prevRange至 result .

Continuous 中的逻辑现在可以:

• 对范围执行二进制搜索，找到最后一个范围 start小于或等于 start .
• 如果这个范围的 end大于或等于 end , 返回 true ;否则，返回 false .