Author: Bhuvnesh Jain
Tester: Ankit Sultana
Editorialist: Eklavya Shama
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.
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