查找Long(在列表中)是否可以适合Long值列表

Question

我有一个List<Long>(A)表示可用于不同分区的可用大小.用户来询问List<Long>(B)表示他们想要存储的文件大小.

现在,如果任何Long(来自B)可以适合A中的任何空闲大小,我们希望重新使用该分区,否则为它们创建新分区.

如何知道LongB中的任何值是否小于LongA中的任何值.

如果我使用迭代方法扫描A并找出B是否适合任何一个,它将导致O(n ^ 2)运行时,但我们能做得更好吗？

这种问题是否存在任何数据结构？

Answer 1

这是一个 O(n) 的解决方案：

鉴于：

List<Long> A; // size n
List<Long> B; // size m

找到 2 条边：

long a = Collections.max(A);  // O(n)
long b = Collections.min(B);  // O(m)

然后看看最大的A能否容纳下最小的B：

boolean canFit = a >= b; // O(1)

总体时间复杂度为 O(n + m)，其中 n 约等于 m 时为 O(n)。