USACO 2018 December Bronze Contest Q2. The Bucket List

import java.util.*;
* Slowest time: 302 ms
* Finds the maximum number of buckets used by utilizing custom comparators and objects
This problem is very similar to the CSES problem Restaurant Customers :
This solution code is basically the solution/algorithm (
as that CSES problem but just slightly modified to fit this USACO problem.
public class TheBucketList {

// Create a Cow class to store each Cow Object as well as their respective times and types (the type is
// essentially just the number of buckets they need)
// if the type has a positive value, that means that the number of buckets is for an arrival time
// if the type has a negative value, then it is past that cow's departure time (for more clarification
// see the USACO guide explanation for Restauarant Customers:
static class Cow {
int time;
int type;

// A comparator to sort the Cow objects in an array
// We use comparators since a Cow object is not a typically library data type like a String or
// Integer so Arrays.sort() or Collections.sort() by itself will not sort the Cow array
// Comparators are used to sort custom objects or values in a non-default order
// In this case, we are sorting the Cows by their time (regardless if it is an arrival or departure time)
static class CowComparator implements Comparator<Cow> {
public int compare (Cow one, Cow two) {return, two.time);}
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
Kattio io = new Kattio("blist");

int N = io.nextInt();

Cow[] data = new Cow[2 * N]; // Cow object array
for (int i = 0; i < N; i++)
Cow arriveCow = new Cow();
// Cow object to store its arrive time and buckets
Cow departCow = new Cow(); // Cow object to store the departure time and buckets
arriveCow.time = io.nextInt();
departCow.time = io.nextInt();
int buckets = io.nextInt();
arriveCow.type = buckets;
departCow.type = -buckets;
// Since it's a departure time, the buckets will be a negative value

data[2 * i] = arriveCow; // insert these Cows into the array
data[2 * i + 1] = departCow;

Arrays.sort(data, new CowComparator()); // Sort the array by the Cow times

// sum is a prefix sum or variable that stores the current number of buckets used at this time
int sum = 0;
// answer stores the largest sum value so far
int answer = 0;
for (Cow cow : data) // Iterate through the array
sum += cow.type;
answer = Math.max(answer, sum);

}static class Kattio extends PrintWriter {
private BufferedReader r;
private StringTokenizer st;

// standard input
public Kattio() { this(, System.out); }
public Kattio(InputStream i, OutputStream o) {
r = new BufferedReader(new InputStreamReader(i));
// USACO-style file input
public Kattio(String problemName) throws IOException {
super(new FileWriter(problemName + ".out"));
r = new BufferedReader(new FileReader(problemName + ".in"));

// returns null if no more input
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(r.readLine());
return st.nextToken();
} catch (Exception e) { }
return null;

public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Annie Zhang

Annie Zhang


Hi! I'm Annie, a high school sophomore and coding enthusiast.