如何确定范围列表是否覆盖给定的范围？

Question

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

我尝试实现一个如下所示的Continuous函数，该函数检查字节范围的片段是否包含给定的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方法(或您希望调用它的任何名称)，该方法将获取一个切片，并返回一个新的切片，其中包含排序的范围和合并的所有重叠范围。对于任何给定的范围集，只需调用Condense一次。然后，Continuous可以要求仅在Condense的结果上调用它。(要强制执行此要求，最好让Condense实际返回一个自定义类型的struct，该类型只是一个片的包装器，并且只在该struct类型上定义Continuous。如果您愿意-为了方便起见-您可以定义一个单独的Continuous方法，该方法可以直接在片上调用，该方法先调用Condense，然后调用Continuous。当然，这种方便的方法将再次变慢，但对于只检查一次的集合来说，它可能是方便的。)

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

如果切片是空的，只需返回它(提前退出)。根据它们的start.

• Create对称为result.

• Initialize range.

• Iterate的新切片进行排序，直到范围内的第一个prevRange。对于每个range.

：

• 如果当前范围在prevRange.end + 1之后开始，则将prevRange添加到result，然后将prevRange设置为当前range.

如果当前范围在prevRange.end之后结束，则将prevRange.end设置为当前end

​

• 将prevRange添加到result.

Continuous中的逻辑现在可以是：

• 对范围执行二进制搜索，查找start小于或等于end的最后一个范围。此范围的end大于或等于true，返回true；否则返回false.

Answer 2

更简单的解决方案？

package main

import (
    "fmt"
    "sort"
)

type byteRange struct {
    start int64
    end   int64
}

type byteRanges []*byteRange

func (brs byteRanges) Continuous(start int64, end int64) bool {
    sort.Slice(brs, func(i, j int) bool {
        return brs[i].start < brs[j].start
    })

    var (
        longestReach int64
        in           bool
    )

    for _, br := range brs {
        if !in {
            // first br satrts laying over the target
            if br.start <= start && br.end >= start {
                longestReach = br.end
                in = true
            }
            continue
        }
        if in && longestReach < br.start-1 {
            break
        }
        if longestReach < br.end {
            longestReach = br.end
        }
    }

    return in && longestReach >= end
}

func main() {
    brs := byteRanges{{5, 9}, {6, 10}}
    fmt.Println(brs.Continuous(8, 10))
}