USACO Guide: Lemonade Line

The Problem

The problem text is shown below (USACO Page):

Problem Text (http://www.usaco.org/index.php?page=viewproblem2&cpid=835)

My Solution

import java.io.*;
import java.util.*;

public class LemonadeLine {
    private static String fileNamePrefix = "lemonade";

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(fileNamePrefix + ".in"));
        StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());

        int numCows = Integer.parseInt(stringTokenizer.nextToken());
        Integer[] maxWaitTimes = new Integer[numCows];

        stringTokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < numCows; i++) {
            maxWaitTimes[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        reader.close();

        Arrays.sort(maxWaitTimes, Collections.reverseOrder());

        PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter(fileNamePrefix + ".out")));

        int numWaiting = 0;

        for (int i = 0; i < maxWaitTimes.length; i++) {
            if (numWaiting <= maxWaitTimes[i])
                numWaiting++;
        }

        writer.println(numWaiting);

        writer.close();
    }
}

Explanation

My code first reads in the information from the input file:

BufferedReader reader = new BufferedReader(new FileReader(fileNamePrefix + ".in"));
StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());

int numCows = Integer.parseInt(stringTokenizer.nextToken());
Integer[] maxWaitTimes = new Integer[numCows];

stringTokenizer = new StringTokenizer(reader.readLine());
for (int i = 0; i < numCows; i++) {
    maxWaitTimes[i] = Integer.parseInt(stringTokenizer.nextToken());
}

reader.close();

Then I sort the array in decreasing order (the cow willing to wait in the longest line is at index 0):

Arrays.sort(maxWaitTimes, Collections.reverseOrder());

After analyzing the problem and running through multiple example test cases on a piece of paper, I realized that the smallest possible line is always obtained when the cows arrive in this order (in order of decreasing willingness to wait for lemonade). It comes down to simple logic: when the cows who are least willing to wait are faced with longer lines, many more cows will leave when compared to the reverse order.

Finally, I run through the array once, making an O(n) algorithm that will perform with large amounts of cows well. In the loop, I check if the cow that has just arrived is willing to wait in the line and adjust the length of the line accordingly:

int numWaiting = 0;

for (int i = 0; i < maxWaitTimes.length; i++) {
    if (numWaiting <= maxWaitTimes[i])
        numWaiting++;
}

Thus we are left with the shortest possible length of the line, the desired answer, and all that is left is to simply output it to a file:

writer.println(numWaiting);

writer.close();

Results

This solution successfully passes all test cases without exceeding the memory or runtime limits, as seen below:

Successful test cases