Problem Statement |
| | You have a few very large files and they need to be sorted according to a total order that is defined for them. The only information you can use to sort them is the relative orders of pairs of files. Unfortunately, finding the relative order of a pair takes N*M minutes where N and M are the sizes of the two files being compared. Given the sizes of the files being sorted, your task is to find a comparison plan that guarantees you will find the correct order in the minimal amount of time. You should return that minimum. |
| |
Definition |
| | | Class: | BasicSorting | | Method: | minSortTime | | Parameters: | int[] | | Returns: | int | | Method signature: | int minSortTime(int[] sizes) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | No two files are 'equal' -- one of them always belongs strictly after the other in the ordering. |
| |
Constraints |
| - | sizes will contain between 2 and 6 elements, inclusive. |
| - | Each element of sizes will be between 1 and 100, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 11 | | With 3 files, you must compare all 3 pairs of files to figure out the order. The total time is thus 1*2 + 1*3 + 2*3 = 11 minutes. |
|
|
| 1) | |
| | | Returns: 5 | | One way to do this is to find the order on three of the files, which takes 3 minutes. Then, compare the fourth file to the middle one of those three files. Finally, if the fourth file comes after the middle file, compare it to the last file, while if it comes before the fourth file, compare it to the first file. |
|
|
| 2) | |
| | |