You have a set of n files of sizes f1, f2, f3,...,fn that you want to store in a hard disk. The disk is divided into segments, each of size K. We make the assumptions that: (i) Each file is of size K (ii) There are at least n segments. Furthermore, the files f1, f2, f3,...,fn subject to the following constraints: i) A file cannot be fragmented ii) A file must be located on only one of the segments The problem is to find a way to store the files on the disk using the minimum number of segments. For example, if K=1 and you have 5 files of sizes 0.2, 0.3, 0.6, 0.3 and 0.5, the best solution would be to use only two best solution would be to use only two segments by putting the files of size 0.3 and 0.6 in one segment and the others in the second segment.

Suggest a way to obtain a non-trivial lower bound on the total number of segments for this problem. (The lower bound of 1 segment is a trivial bound; try to find one that is more general.) Consider the following voracious heuristic: 1) Sort the files from largest to smallest 2) Consider the files in this order and put, in each phase, the next file F in the segment that has the smallest available space (but enough to contain it). Find an example, for K=2, where this heuristic does not give the optimal solution (show that there is at least one solution that uses fewer segments than the example).