# Problem Link

**Author:** Bhuvnesh Jain

**Tester:** Ankit Sultana

**Editorialist:** Eklavya Shama

# Difficulty

Easy

# Prerequisites

Priority queue

# Problem

You are given sizes of several arrays.

You have to find out the optimal order for merging these arrays such that

the worst-case number of element comparisons are minimum.

You have to output the total number of comparisons in the worst case for this order.

# Explanation

When two arrays of size m and n are merged, the worst case number of comparisons is m + n - 1

and size of the resultant array is of size m + n.

The optimal merging strategy is greedy, i.e. keep merging the shortest two arrays until just one array remains.

This can be efficiently done using a priority queue.

```
s = 0
Insert n1, n2, ..., nM in the priority queue.
While there is more than 1 element in the priority queue:
Pop the smallest 2 elements from the priority queue. Let these be x and y.
s = s + x + y - 1;
Insert x + y in the priority queue.
output s
```

# Time complexity

O(M*log(M))