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
I have tried to implement it without priority queue. Instead I have used an array. The solution goes like -
while(j++ < testCases) {
M = fs.nextInt();
int sum = 0, result = 0;
arraySize = new int[M];
for (int a = 0; a < M; a++) {
arraySize[a] = fs.nextInt();
}
Arrays.sort(arraySize);
// System.out.println(sum);
for(int i = 0; i < M; i++) {
sum += arraySize[i];
if(i == 0) {
} else {
result += sum - 1;
}
}
System.out.println(result);
}
ACC to your algo, for 3 4 5 the answer is 17 but what if we first sort 4 and 5 with answer 8 and then sort 3 and 9(4+5), in this way it gives 19. Where am I wrong?
To decrease number of total operations, you should always chose the minimum sizes of array to reduce number of comparisons. You do it the other way around.
