c++ - 查找 x 轴上最大非重叠线数的算法

Question

我不太确定如何提出这个问题，但我会尽量具体些。 想象一个俄罗斯方 block 屏幕，只有不同形状的矩形，落到底部。 我想计算我可以一个接一个放置而没有任何重叠的矩形的最大数量。我在标题中将它们命名为线，因为我实际上只对计算时矩形的长度感兴趣，或者它落向的平行于 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。因此，在对这个列表进行排序时，我必须删除第 2 个或第 3 个对象，以免它们重叠。

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

我用 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) .我们有等式(这是 latex ):

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