Sunday, August 3, 2014

DiskSpace

Problem:

TopCoder Problem Statement - DiskSpace

Overview:

Determine the smallest number of hard drives needed to store all your stuff.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 156
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1777
08:  */
09:
10: import java.util.Arrays;
11:
12: public class DiskSpace {
13:
14:     public int minDrives(int[] used, int[] total) {
15:
16:         int capacityNeeded = 0;
17:
18:         // Calculate the total amount of space needed.
19:         for (int u : used) {
20:             capacityNeeded += u;
21:         }
22:
23:         /*
24:          * Sort the drive capacitites.
25:          * Then we'll start filling from the largest disc working back to the
26:          * smallest.
27:          */
28:         Arrays.sort(total);
29:
30:         // Start with the largest drive.
31:         int i = total.length - 1;
32:
33:         // The number of drives needed.
34:         int count = 0;
35:
36:         while (capacityNeeded > 0) {
37:             count++;
38:
39:             // Subtract the current drive's capacity from the amount needed.
40:             capacityNeeded -= total[i--];
41:         }
42:
43:         return count;
44:     }
45: }
Notes:

This solution is a simple example of using a greedy algorithm. We'll fill up the largest drives first, and use up smaller and smaller drives as necessary.

The first step is to determine the toal amount of space that your data requires. This is calculated by the for loop starting on line 19, and is stored in the variable capacityNeeded.

Next, the drives are sorted by their capacity using Arrays.sort(). This will arrange the array with the smallest element first.

Finally, we begin filling the drives, beginning with the largest one at the end of the total[] array and working backward to the smaller drives. For each drive, we subtract their volume from capctiyNeeded, until capacityNeeded is no longer greater than zero.

We don't need to worry about not having enough space, because the problem statement guarantees that the capacity of the drives will be large enough.

Also, it's good to remember that Java provides the methods Arrays.sort() and Collections().sort for sorting.

No comments:

Post a Comment