时间：   |   分类：     |   阅读： 988 字 ~2分钟

最近做一个业务涉及到检测区间是否全覆盖的问题,具体来说就是填写的区间段有没有断开的情况

--连续
[1,2]
[3,4]

--非连续
[1,2]
[4,5]

--非连续
[1,2]
[3,4]
[2,3]
[6,7]

这个其实可以转换成两个区间是否有相交性的问题,搜集总结一下相交性推导的算法

范围是否相交

[A,B]和 [X,Y] 两个范围是否有相交,前提是A<=B并且X<=Y 最直观的做法做排列组合

排列组合

A B X Y
A X B Y  intersect
A X Y B  intersect
X A B Y  intersect
X A Y B  intersect
X Y A B

可以看到相交的四种情况

local function check_overlap(a, b, x, y)
    return (a >= x and a <= y) or
         (b >= x and b <= y) or
         (x >= a and x <= b) or
         (y >= a and y <= b)
end

用另外两种不相交的情况更简单

local function check_overlap(a, b, x, y)
    return not (b < x or y < a)
end

推导出相交的情况

local function check_overlap(a, b, x, y)
    return (b >= x and y >= a)
end

另外一种推导

---------
a___b
   x___y
----------

可以看出两个范围要相关要满足条件 首尾数值差值(y-a)要小于a,b段差值加上x,y段差值

local function check_overlap(a, b, x, y)
    return math.max(b, y) - math.min(a, x) <= (b - a) + (y - x)
end

另外一种推导

local function check_overlap(a, b, x, y)
    return math.max(a,x) <= math.min(b,y)
end

检查数组中范围是否有断开

基于上面的相交算法,这个检测就比较好做了,思路是把相交的范围归纳为同一个组,如果有一个组以上就说明中断开未全覆盖的情况,代码如下:

local t = {
    {1, 50},
    {51, 60},
    {40, 52},
    {72, 78}}

local in_rangs = {}
local rangs_min_max = {}

for k, v in ipairs(t) do
    local s_min = v[1]
    local s_max = v[2]
    for k1, value in ipairs(t) do
        local c_min = value[1]
        local c_max = value[2]
        --业务中为闭区间,[1,2] [3,4]当作是连续的
        if s_min < c_max and c_min <= s_max + 1 then
            local k_idx = in_rangs[k]
            if not k_idx then
                k_idx = k
                in_rangs[k] = k_idx
            end
            in_rangs[k1] = k_idx

            local min_max = rangs_min_max[k_idx]
            if not min_max then
                min_max = {min = s_min, max = s_max}
                rangs_min_max[k_idx] = min_max
            end
            if c_min < min_max.min then
                min_max.min = c_min
            end
            if c_max < min_max.max then
                min_max.max = c_max
            end
        end
    end
end
for key, value in pairs(in_rangs) do
    print(key, value)
end
local count = 0
for key, value in pairs(rangs_min_max) do
    print(key, value.min, value.max)
    count = count + 1
end
print(count > 1)

输出

1	1
2	1
3	1
4	4

1	1	50
4	72	78

true

分隔所有段

进阶的做法是可以将所有范围按相交点切割,游戏中实际需求是是要查询各个等级下面有哪些对应的物品,按正常的做法是要遍历所有项,比对是否满足这个等级条件.更省cpu的做法是将可各个等级段下有哪些物品先做预处理.比如配置

[1,3] --> a
[4,7] --> b
[1,5] --> c

转换成全等级段为
[1,3] --> a,c
[4,5] --> b,c
[6,7] --> b

预处理代码如下:

local t = {
    {1, 50},
    {51, 60},
    {40, 52},
}

local s = {}
for _, value in pairs(t) do
    s[value[1]] = true
    s[value[2]] = true
end

local r = {}
for key, _ in pairs(s) do
    table.insert(r, key)
end
table.sort(r, function(a, b)
    return a < b
end)

local big_all_lvs = {}
local last_end
for idx, curr in ipairs(r) do
    if idx == 1 then
        goto CONTINUE
    end
    local last = r[idx - 1]
    local begin = last_end and last_end + 1 or last
    if begin == curr then
        goto CONTINUE
    end
    table.insert(big_all_lvs, {server_lv = {min = begin, max = curr}, datas = {}})
    last_end = curr
    ::CONTINUE::
end

for idx, value in ipairs(t) do
    local min = value[1]
    local max = value[2]
    for _, l in ipairs(big_all_lvs) do
        local lvs = l.server_lv
        if min < lvs.max and lvs.min < max then
            table.insert(l.datas, idx)
        end
    end
end

for _, l in pairs(big_all_lvs) do
    local lvs = l.server_lv
    local datas = l.datas
    print(lvs.min, lvs.max)
    print(table.concat(datas, ","))
    print("-------------------------")
end

输出

1	40
1
-------------------------
41	50
1,3
-------------------------
51	52
2,3
-------------------------
53	60
2
-------------------------

参考 + https://stackoverflow.com/questions/3269434/whats-the-most-efficient-way-to-test-two-integer-ranges-for-overlap/3269471#3269471 + http://world.std.com/~swmcd/steven/tech/interval.html

0%