Find if a Long ( in a list ) can fit in a List of Long values

Question

I've a List<Long> (A) indicating the free sizes available for different partitions. Users come to ask with a List<Long> ( B) indicating the file sizes they want to store.

Now if any Long (from B) can fit into any free size in A, we want to re-use the partition, otherwise create new partition for them.

How can I know if any of the Long value from B have value less than any of the Long in A.

If I use iterative approach to scan through A and find out if any of B will fit, it will cause O(n^2) runtime, but can we do better ?

Any Data structure exists for this kind of problem ?

Answer 1

Here's an O(n) solution:

Given:

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

Find the 2 edges:

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

Then see if the largest A can fit the smallest B:

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

Overall time complexity O(n + m) which for n approx equal to m is O(n).