title: How Improve Run-time when sorting arrays
body: <p>I have managed to create a working solution for "Mixing Milk" for USACO, but the judge says my program takes too long. </p>
  
  <p>I think this has to do with the way I sort the list of Farmers by asking price in lines 29 - 44. Is there any way I can improve the run time?</p>
  
  <pre><code>/*
   ID:
   LANG: JAVA
   TASK: milk
   */
  import java.util.*;
  import java.io.*;
  
  public class milk {
  
      public static void main(String[] args) throws IOException {
          double startTime = System.currentTimeMillis();
          BufferedReader s = new BufferedReader(new InputStreamReader(new FileInputStream(new File("test.in"))));
          PrintWriter w = new PrintWriter(new File("test.out"));
  //        BufferedReader s = new BufferedReader(new InputStreamReader(new FileInputStream(new File("milk.in"))));
  //        PrintWriter w = new PrintWriter(new File("milk.out"));
          String[] st = s.readLine().split(" ");
          int N = Integer.parseInt(st[0]);
          int M = Integer.parseInt(st[1]);
          int[] P = new int[M];
          int[] A = new int[M];
          String[] sets = new String[M];
          for (int i = 0; i &lt; M; i++) {
              sets[i] = s.readLine();
              st = sets[i].split(" ");
              P[i] = Integer.parseInt(st[0]);
          }
          int maxp = ("" + maxVal(P)).length();
          for (int i = 0; i &lt; M; i++) {
              st = sets[i].split(" ");
              while (st[0].length() &lt; maxp) {
                  st[0] = "0" + st[0];
              }
              sets[i] = st[0] + " " + st[1];
          }
          Arrays.sort(sets);
          int cap = 0;
          for (int i = 0; i &lt; M &amp;&amp; cap &lt;= N; i++) {
              st = sets[i].split(" ");
              P[i] = Integer.parseInt(st[0]);
              A[i] = Integer.parseInt(st[1]);
              cap += A[i];
          }
          int sum = 0;
          int units = 0;
          int a;
          for (int i = 0; units &lt; N; i++) {
              if (A[i] &lt;= N - units) {
                  sum = sum + P[i] * A[i];
                  units += A[i];
              } else {
                  a = N - units;
                  if (a &gt; A[i]) {
                      a = A[i];
                  }
                  sum = sum + P[i] * a;
                  units += a;
              }
          }
          System.out.println(units);
          System.out.println(sum);
          w.println(sum);
          w.close();
          double endTime = System.currentTimeMillis();
          System.out.println("Took " + ((endTime - startTime) / 1000) + " seconds.");
      }
  
      public static int maxVal(int[] x) {
          int max = 0;
          for (int i : x) {
              if (i &gt; max) {
                  max = i;
              }
          }
          return max;
      }
  }
  </code></pre>
  
  <p>EDIT: Thanks Andreas!</p>
  
  <p>Changed code and made the time limit:</p>
  
  <pre><code>/*
   ID:
   LANG: JAVA
   TASK: milk
   */
  
  import java.util.*;
  import java.io.*;
  
  public class milk {
  
      public static void main(String[] args) throws IOException {
          double startTime = System.currentTimeMillis();
  //        BufferedReader s = new BufferedReader(new InputStreamReader(new FileInputStream(new File("test.in"))));
  //        PrintWriter w = new PrintWriter(new File("test.out"));
          BufferedReader s = new BufferedReader(new InputStreamReader(new FileInputStream(new File("milk.in"))));
          PrintWriter w = new PrintWriter(new File("milk.out"));
          String temp = s.readLine();
          int spc = temp.indexOf(" ");
          int N = Integer.parseInt(temp.substring(0, spc));
          int M = Integer.parseInt(temp.substring(spc + 1));
          System.out.println(N + " " + M);
          int[] P = new int[M];
          int[] A = new int[M];
          Farmer[] f = new Farmer[M];
          for (int i = 0; i &lt; M; i++) {
              temp = s.readLine();
              spc = temp.indexOf(" ");
              f[i] = new Farmer(Integer.parseInt(temp.substring(0, spc)), Integer.parseInt(temp.substring(spc + 1)));
          }
          Arrays.sort(f);
          for (int i = 0; i &lt; M; i++) {
              P[i] = f[i].getPrice();
              A[i] = f[i].getInventory();
          }
          int sum = 0;
          int units = 0;
          int a;
          for (int i = 0; units &lt; N; i++) {
              if (A[i] &lt;= N - units) {
                  sum = sum + P[i] * A[i];
                  units += A[i];
              } else {
                  a = N - units;
                  if (a &gt; A[i]) {
                      a = A[i];
                  }
                  sum = sum + P[i] * a;
                  units += a;
              }
          }
          System.out.println(units);
          System.out.println(sum);
          w.println(sum);
          w.close();
          double endTime = System.currentTimeMillis();
          System.out.println("Took " + ((endTime - startTime) / 1000) + " seconds.");
      }
  }
  
  class Farmer implements Comparable&lt;Farmer&gt; {
  
      private int price;
      private int inventory;
  
      public Farmer(int price, int inventory) {
          this.price = price;
          this.inventory = inventory;
      }
  
      public int getPrice() {
          return price;
      }
  
      public int getInventory() {
          return inventory;
      }
  
      @Override
      public int compareTo(Farmer f1) {
          if (f1.price != this.price) {
              return this.price - f1.price;
          } else if (f1.inventory != this.inventory) {
              return f1.inventory - this.inventory;
          } else {
              return 0;
          }
      }
  }
  </code></pre>