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

user_870382 0
Viewed 91

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 ?

time-complexity collections java
2 Answers

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).

user_2561960

You should look at the NavigableSet interface. Store in such a set the available partitions with a sort key of size. Then use the ceiling operator to find the smallest partition at least as large as the desired one. NavigableSet also supports add and remove operations, which is all you need to maintain the partition list dynamically.

Sensible implementations of NavigableSet like TreeSet provide O(log n) performance for all three operations, where n is the number of available partitions. When you allocate one, you'll want to remove it and re-insert the remaining sliver with a smaller key.

Another approach is to use an an array of logarithmically-sized buckets. This is what malloc-like memory allocators tend to do. They will not match size requests to available blocks as accurately as the approach above, but they'll be very close to constant time. See the discussion here for an example with details.

user_11618780
Related