USACO 2018 December Bronze Contest Q2. The Bucket List

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()); }
}
}

--

--

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

9 Followers

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