Given an array F with size n.Assume the array content F[i] indicates the length of the ith file and we want to merge all these files into one single file.Devise an optimal solution for this
Lets say Given array is F={10,5,100,50,20,15}
Greedy Appraoch---
1.Store filesizes in a priority queue.The key of elements are file lengths.
2.Repeat the following until there is only 1 file
a.Extract two smallest elements X & Y
b.Merge X & Y and insert this new file in the priority queue.
Using above approach total cost of merging is 15+30+50+100+200=395
Time complexity:O(nlogn)
Lets say Given array is F={10,5,100,50,20,15}
Greedy Appraoch---
1.Store filesizes in a priority queue.The key of elements are file lengths.
2.Repeat the following until there is only 1 file
a.Extract two smallest elements X & Y
b.Merge X & Y and insert this new file in the priority queue.
Using above approach total cost of merging is 15+30+50+100+200=395
Time complexity:O(nlogn)
No comments:
Post a Comment