USACO Guide: Cow Dance Show

The Problem

The problem text is shown below (USACO Page):

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

Explanation

Whenever I see a problem looking for the highest/lowest possible value for a number that determines how some process is performed, I think about binary searching for the answer. Implementing a binary search for K is quite simple: the minimum possible stage size is 1 cow, the maximum possible stage size is N, the size of the herd. From there, implementing a binary search that adjusts the upper and lower bounds if a certain K value is valid is trivial.

Thus, we are left with the other part of the problem: validating K values. As we are using timed events that occur in a specific order, I thought to use a PriorityQueue. My code cycles through each cow in order of arrival, and adds them to the PrioirityQueue if there is space on the stage. When the stage is full, it updates a variable that keeps track of the last timed event and skips ahead to when the first cow on the stage exits. For each cow, a check is done to see if it is possible for the cow to complete its dance without exceeding the time limit. If not, then there is no need to continue the rest of the loop or check any other cows, and false is returned. If the loop finishes without false being returned, then true is returned, as the show has finished.

My Solution

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

public class CowDanceShow {
    private static String fileNamePrefix = "cowdance";
    private static int numCows, maxTime;
    private static int[] cowDanceTimes;

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

        numCows = Integer.parseInt(stringTokenizer.nextToken());
        maxTime = Integer.parseInt(stringTokenizer.nextToken());

        cowDanceTimes = new int[numCows];

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

        reader.close();

        // Binary search the smallest possible value of K that works
        int min = 1, max = numCows;
        while (min != max) {
            int mid = (min + max) / 2;

            if (validK(mid))
                max = mid;
            else
                min = mid + 1;
        }

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

        writer.println(min);

        writer.close();
    }

    private static boolean validK(int k) {
        int lastEventTime = 0;
        PriorityQueue<Integer> danceQueue = new PriorityQueue<>();
        for (int i = 0; i < cowDanceTimes.length; i++) {
            if (danceQueue.size() == k)
                // Stage is full, go to next event
                lastEventTime = danceQueue.poll();
            if (lastEventTime + cowDanceTimes[i] > maxTime)
                // This cow would dance past the time limit, so this is not valid
                return false;
            danceQueue.add(lastEventTime + cowDanceTimes[i]); // Add the next event
        }

        return true; // All cows danced without passing the time limit
    }
}

Results

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

Successful test cases