如何提高根据具体情况排砖的时间复杂度？

Question

我正在解决一个问题，需要将 N 块不同长度的砖块排列成最少数量的砖块。堆砖的规则是，一块砖 𝑖 可以放置在砖块顶部 𝑗 仅当条件满足时 𝐴𝑖 + 𝑥 ≤ 𝐴𝑗 成立，其中 𝑥 是给定的整数。

这是我当前在 Python 中的实现：

def arrange_bricks(N, x, bricks):
    # Sort the bricks in descending order
    bricks.sort(reverse=True)

    # List to hold stacks
    stacks = []

    for brick in bricks:
        placed = False
        for stack in stacks:
            if brick + x <= stack[-1]:
                stack.append(brick)
                placed = True
                break
        
        if not placed:
            stacks.append([brick])

    print(len(stacks))
    for stack in stacks:
        print(len(stack), ' '.join(map(str, stack)))

N, x = map(int, input().split())
bricks = list(map(int, input().split()))
arrange_bricks(N, x, bricks)

问题： 时间复杂度：目前，我的解决方案的时间复杂度是 在最坏的情况下𝑂(𝑁^2)，因为每个砖块都可能会检查所有现有的堆栈。这可能效率低下，尤其是当 𝑁很大（最多10^6）。

期望的结果：我想提高时间复杂度以提高效率，如果可能的话最好在 𝑂(𝑁log𝑁) 左右。

限制：

• 1 ≤ 𝑁 ≤ 10^6

• 1 ≤ 𝑥 ≤ 10^9

• 1 ≤ 𝐴𝑖 ≤ 10^9

问题： 如何修改我的方法以使用更有效的数据结构或算法来降低时间复杂度？ 我可以应用特定的算法或技术来更有效地解决这个问题吗？ 谢谢您的帮助！

Answer 1

一个简单的贪心算法就可以解决问题。

首先，将砖块按降序排序，a1 >= a2 >= ... >= an。

观察1：对于堆栈，我们只需要存储顶部砖块的长度。

我们将砖块一一放入，并维护 S 中当前堆栈顶部砖块的排序长度。对于每个砖块 ai，我们找到 S 中最短的顶部砖块，以便将 ai 放在顶部（si > = ai + x) 如果存在这样的顶部砖块，则将 ai 放在顶部。否则，我们需要开始一个新的堆栈并将ai作为基础砖块。搜索最短的顶部砖块以便将 ai 放在顶部可以通过对排序列表 S 进行二分搜索来完成。

观察 2：这是最佳的。可以通过交换论证来证明。

交换论据概要如下：

假设最优解决方案使用 n 个堆栈 T = {stack_1, stack_2, ..., stack_n}，而我们的算法使用 m 个堆栈 S = {stack_1, stack_2, ..., stack_m}。

我们确定 a1 在 T 中的位置，比如 stack_i。 a1 必须位于 stack_i 的底部。

现在，如果 a2 + x <= a1 but a2 is not on top of a1 in T, a2 must be at the base of another stack stack_j where i != j. We can swap {stack_i minus a_1} with {stack_j} and the resulted set T' will also be a valid solution with n stacks where the first step of putting a2 matches with our algorithm. We repeat the exchange process recursively by ignoring a1 from T and focuses on {a2, ..., an}

否则，如果 a2 + x > a1，则 a2 必须位于某个 stack_j 的底部，使得 i != j。这与我们的算法相符。我们通过忽略 T 中的 a1 并专注于 {a2, ..., an} 来递归地重复交换过程。

最后，在堆栈数量不变的情况下，集合T将变换为S，证明|S| = |T|。