Q: which is the optimal type of collection?

Vidal09

I've been asked to program a solution for the 2016 ICPC World Finals problem L, as a homework.

I've managed to successfully create and run a program that solves the problem in question. However, I'm curious if there is a better way to manage data because when i execute this with the maximum amount of disk(1000000) doesnt finish in the required time of execution.

made with 100000 disk because it 1000000 doesnt get to finish or takes over 6 minutes

translate "swap necessary is 714 gb"

Problem L is as follows:

You administer a large cluster of computers with hard drives that use various file system types to store data. You recently decided to unify the file systems to the same type. That is quite a challenge since all the drives are currently in use, all of them are filled with important data to the limits of their capacities, and you cannot afford to lose any of the data. Moreover, reformatting a drive to use a new file system may significantly change the drive’s capacity. To make the reformat possible, you will have to buy an extra hard drive. Obviously, you want to save money by minimizing the size of such extra storage. You can reformat the drives in any order. Prior to reformatting a drive, you must move all data from that drive to one or more other drives, splitting the data if necessary. After a drive is reformatted, you can immediately start using it to store data from other drives. It is not necessary to put all the data on the same drives they originally started on – in fact, this might even be impossible if some of the drives have smaller capacity with the new file system. It is also allowed for some data to end up on the extra drive.

The input begins with a line containing one integer n (1 ≤ n ≤ 106 ), which is the number of drives in your cluster. Following this are n lines, each describing a drive as two integers a and b, where a is the capacity with the old file system and b is the capacity with the new file system.

Am using a greedy aproach to solve this in which I need to sort this on certain way that creates 2 list's

public static class Disk { // creates object disk with initial size and final size            private int a;//initial                private int b;//final                public Disk(){                        this.a = ThreadLocalRandom.current().nextInt(1, 15 + 1);            this.b = ThreadLocalRandom.current().nextInt(1, 15 + 1);        }                public int getA(){            return this.a;}                 public int setA( int n){            return a = n;}                 public int getB(){            return b;}                 public int setB( int n){            return b = n;}                  }    public static void Split(ArrayList <Disk> diskList, ArrayList <Disk> grow, ArrayList <Disk> shrink){        //Split between disk that gain space and disk that lose space after formating         for (int i =0; i < diskList.size(); i++){                        if (diskList.get(i).getA() > diskList.get(i).getB()){                            shrink.add(diskList.get(i));            }            else{                              grow.add(diskList.get(i));            }        }    }    public static void SortGain(ArrayList <Disk> diskList){//sort disk that gain from smaller to bigger because for the first disk you need swap space then is better star with the smaller        for (int i = 0; i < diskList.size()-1; i++){                        for (int j = 0; j < diskList.size()-1; j++){                                if (diskList.get(j).getA() > diskList.get(j+1).getA()){                                    Collections.swap(diskList, j, j+1);                }            }            }        }        public static void SortLoss(ArrayList <Disk> diskList){        //sort disk that gain from bigger to smaller, analize the biggest disk when you have maximun amount of extra space        for (int i = 0; i < diskList.size()-1; i++){                         for (int j = 0; j < diskList.size()-1; j++){                                 if (diskList.get(j).getA() < diskList.get(j+1).getA()){                    Collections.swap(diskList, j, j+1);                }            }         }      }        public static int GetSwap(ArrayList <Disk> gainList, ArrayList <Disk> lossList){       /*body of the algorithm, every time you need extra space swap get increased if after format        you get extra space it's store on extra         */        int swap = 0;                int extra = 0;                for (int i =0; i < gainList.size()-1; i++){//first go through gain list so you get extra space                        while(swap + extra < gainList.get(i).getA()){//you can use swap and extra to store informaticion if it isn't enought you increse swap                                swap = swap + 1;            }            extra = extra + gainList.get(i).getB() - gainList.get(i).getA();          }        for (int i =0; i < lossList.size()-1; i++){//now you use the same extra space and swap soace but this time you lose space                        while(swap + extra < lossList.get(i).getA()){                                swap = swap + 1;            }            extra = extra + lossList.get(i).getB() - lossList.get(i).getA();          }                return swap;    }        public static void main(String[] args) {//test disk        ArrayList<Disk> list = new ArrayList<Disk>();        ArrayList<Disk> grow = new ArrayList<Disk>();        ArrayList<Disk> shrink = new ArrayList<Disk>();        int n = 500000;                for (int i =0; i<n; i++){                list.add(new Disk());        }                Split(list,grow,shrink);        SortGain(grow);        SortLoss(shrink);        for(int i =0; i< grow.size(); i++){                System.out.println(grow.get(i).getA() + "   "+ grow.get(i).getB());                }        System.out.println("");        System.out.println("");        System.out.println("");        System.out.println("");        System.out.println("");                                        for(int i =0; i< shrink.size(); i++){                    System.out.println(shrink.get(i).getA() + "   "+ shrink.get(i).getB());//show disks                }                int swap = GetSwap(grow, shrink);                System.out.println("El swap requerido son " + swap + " GB");//show results    }

currently am using ArrayList to do it, but i was wondering if there is another type of collection that's more efficient for this problem so i can executed on the amount of time required.to be specific would be better to use something like hash tables, linked list, linked hash set, sorted set, etc

Mensaje editado por: Vidal09