用于在x轴上找到最大数量的非重叠线的算法

Question

我不确定如何问这个,但我会尽量做到具体.想象一个俄罗斯方块屏幕,只有不同形状的矩形,落到底部.我想计算一个接近另一个的矩形的最大数量而不重叠.我在标题中将它们命名为行,因为我实际上只对计算时矩形的长度感兴趣,或者是平行于x轴的线,它正朝着它倾斜.

所以基本上我有一个带开始和结束的自定义类型,两个整数都在0到100之间.假设我们有一个从1到n的矩形列表.rectangle_n.start(除非是最接近原点的矩形)必须是> rectangle_(n-1).end,以便它们永远不会重叠.我正在从具有随机数的文件中读取矩形坐标(都是x轴坐标).

例如:考虑这个矩形类型对象列表

rectangle_list {start, end} = {{1,2}, {3,5}, {4,7} {9,12}}

我们可以观察到第3个对象的起始坐标为4 <前一个矩形的结束坐标为5.因此在排序此列表时,我必须删除第二个或第三个对象,使它们不重叠.

我不确定这种问题是否有类型,所以我不知道如何命名它.我对可以应用在这些对象列表上的算法感兴趣,并相应地对它们进行排序.

我用c ++标记了这个,因为我写的代码是c ++,但任何语言都可以用于算法.

Answer 1

您基本上解决了以下问题.假设我们有n间隔{[x_1,y_1),[x_2,y_2),...,[x_n,y_n)}带x_1<=x_2<=...<=x_n.我们希望找到这些间隔的最大子集,使得子集中的任何间隔之间不存在重叠.

天真的解决方案是动态编程.它保证找到最佳解决方案.设f(i),, 0<=i<=n是最大子集的大小,直到间隔[x_i,y_i).我们有等式(这是乳胶):

f(i)=\max_{0<=j<i}{f(j)+d(i,j)}

其中,d(i,j)=1当且仅当[x_i,y_i),并[x_j,y_j)没有重叠; 否则d(i,j)为零.您可以迭代计算f(i),从f(0)=0.f(n)给出最大子集的大小.要获得实际的子集,您需要保留一个单独的数组s(i)=\argmax_{0<=j<i}{f(j)+d(i,j)}.然后,您需要回溯以获得"路径".

这是一个O(n^2)算法:你需要计算每一个f(i)和每个f(i)你需要i的试验次数.我认为应该有一个O(nlogn)算法,但我不太确定.

编辑:Lua中的一个实现:

function find_max(list)
    local ret, f, b = {}, {}, {}
    f[0], b[0] = 0, 0
    table.sort(list, function(a,b) return a[1]<b[1] end)
    -- dynamic programming
    for i, x in ipairs(list) do 
        local max, max_j = 0, -1
        x = list[i]
        for j = 0, i - 1 do
            local e = j > 0 and list[j][2] or 0
            local score = e <= x[1] and 1 or 0
            if f[j] + score > max then
                max, max_j = f[j] + score, j
            end
        end
        f[i], b[i] = max, max_j
    end
    -- backtrack
    local max, max_i = 0, -1
    for i = 1, #list do
        if f[i] > max then -- don't use >= here
            max, max_i = f[i], i
        end
    end
    local i, ret = max_i, {}
    while true do
        table.insert(ret, list[i])
        i = b[i]
        if i == 0 then break end
    end
    return ret
end

local l = find_max({{1,2}, {4,7}, {3,5}, {8,11}, {9,12}})
for _, x in ipairs(l) do
    print(x[1], x[2])
end