USACO 2018 December Bronze Contest Q2. The Bucket List

Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=856

Solution:

This solution creates an additional Cow class and a CowComparator class to sort that Cow class. The comparator allows us to sort our custom objects (Cow) in the order that we want because without it, Arrays.sort() and Collections.sort() will only work on the standard library data types such as Integers, ints, Doubles, doubles, Strings, etc. We take in each input line as two cow objects (one to store the arrival time and the buckets needed (time), one to store the departure time of that cow and the buckets needed(type)). The arrival Cow objects will all have a positive type (buckets needed) value while the departure Cow objects will all have a negative type value. After we take in all the input, we insert them into our array, data, and use our CowComparator class that we wrote to sort the array by each cow’s time (regardless if it is arrival or departure). Then, we create two variables, sum (prefix or running sum of the buckets needed at the current time)and answer (stores the maximum number of buckets so far).We iterate through the sorted data array and update our sum and answer variables accordingly, then output answer.

import java.io.*;
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 : https://cses.fi/problemset/task/1619
 This solution code is basically the solution/algorithm (https://usaco.guide/problems/cses-1619-restaurant-customers/solution)
 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: https://usaco.guide/problems/usaco-856-the-bucket-list/solution)
 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 Integer.compare(one.time, 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);
  }
  
  
  
  io.println(answer);
  io.close();
}
static class Kattio extends PrintWriter {
  private BufferedReader r;
  private StringTokenizer st;
 
  // standard input
  public Kattio() { this(System.in, System.out); }
  public Kattio(InputStream i, OutputStream o) {
   super(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()); }
 }
}

Hope this editorial helped you! If so, it would be greatly appreciated if you pressed the clap button on this article or followed me on Medium. If any clarification is needed or if you have any suggestions for improvement, feel free to drop a comment below.