Read Bundle Assembly Budget

Minimum total cost to merge array elements, costing each pair's sum

EasyHeapGreedy

A genetics lab stores sequencing reads in separate bundles. The number of reads in each bundle is given by bundles.

One assembly operation chooses any two current bundles and replaces them with a single bundle containing all their reads. The operation's processing cost equals the sum of the two chosen bundle sizes. The new bundle may be chosen in later operations.

The lab must combine all bundles into one. Return the minimum possible total processing cost over all choices of assembly operations.

If there are fewer than two bundles, return 0. Bundles with the same size are still separate bundles.

Examples

Example 1

Input: bundles = [4,7,2]
Output: 19

For sizes 4, 7, and 2, first combine the bundles of sizes 2 and 4. Then combine the resulting size-6 bundle with the size-7 bundle. This costs less than either other choice for the first operation.

Example 2

Input: bundles = [3,3,3,3]
Output: 24

All four bundles initially have size 3. Combine two pairs separately, then combine the two resulting bundles. Growing one bundle through every operation would cost more.

Example 3

Input: bundles = [12]
Output: 0

There is already only one bundle, so no assembly operation is needed.

Constraints

  • 0 <= bundles.length <= 5000
  • 1 <= bundles[i] <= 1000000
  • The result is an integer and may exceed the signed 32-bit range.

The intended solution takes O(n log n) time and O(n) extra space. All possible results within the constraints are exactly representable by JavaScript numbers.

Hints

Show hint 1

Which two bundles should be combined first to avoid repeatedly charging for large bundles?

Show hint 2

Use a min-heap to retrieve the two smallest current sizes and insert their combined size.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you also return one optimal sequence of operations, using original indices and newly assigned bundle IDs?
  • If the initial sizes are already sorted, can you compute the same result in linear time using two queues?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem