You are given n les of size s1; s2; :::; sn. You may merge any two files i; j in

Question

You are given n les of size s1; s2; :::; sn. You may merge any two files i; j into a file of size
si + sj in total time si + sj . You want to merge all n files into a single file in the minimum
possible amount of time. Devise a greedy algorithm to solve this problem, and justify the
correctness of your algorithm (you do NOT need to formally prove it).
Example: s1 = 1; s2 = 2; s3 = 3. If you merge s1 with s2, this takes 3 time units and makes
s12 of size 3. We can then merge s12 with s3 in 6 time units. So we can merge all three les
in 9 time units.

Explanation / Answer

make a merge function which takes two array of size n1 and n2 and returns the merged array. it will also take the result array as the input argument. each time from the main function when we call this function with 2 arrays we reallcoate the space for the result array by the size of the new array going to be merged. in this way we can get the final merged array in O(s1+s2+s3.....sn) time

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.