This is the Internal Solution for The Bucket List Problem:
import java.io.*;
import java.util.*;
public class TheBucketList2 {
static final int maxTime = 1000;
public static void main (String[] args) throws IOException {
Kattio io = new Kattio("blist");
int n = io.nextInt();
int[] startTimes = new int[n + 1];
int[] endTimes = new int[n + 1];
int[] bucketsNeeded = new int[n + 1];
// these track when the cows start
int[] cowStart = new int[maxTime + 1];
int[] cowEnd = new int[maxTime + 1];
for (int x = 1; x <= n; x++) {
startTimes[x] = io.nextInt();
endTimes[x] = io.nextInt();
bucketsNeeded[x] = io.nextInt();
cowStart[startTimes[x]] = x;
cowEnd[endTimes[x]] = x;
}
int maxBuckets = 0;
int countBuckets = 0;
for (int t = 1; t <= 1000; t++) {
// is a start, increase the bucket count
if (cowStart[t] > 0) {
countBuckets += bucketsNeeded[cowStart[t]];
}
// keep track of the maximum buckets needed at any time
maxBuckets = Math.max(maxBuckets, countBuckets);
// is an end, decrease the bucket count
if (cowEnd[t] > 0) {
countBuckets -= bucketsNeeded[cowEnd[t]];
}
}
io.println(maxBuckets);
io.close();
}
}
Can someone help me understand how this works? I tried running it and adding print statements to see what it is doing. the part I am having difficulty with is understanding is this part:
for (int t = 1; t <= 1000; t++) {
// is a start, increase the bucket count
if (cowStart[t] > 0) {
countBuckets += bucketsNeeded[cowStart[t]];
}
// keep track of the maximum buckets needed at any time
maxBuckets = Math.max(maxBuckets, countBuckets);
// is an end, decrease the bucket count
if (cowEnd[t] > 0) {
countBuckets -= bucketsNeeded[cowEnd[t]];
}
}
How is this working? Wouldnt cows that begin milking at the same time be overridden in the cowStart and cowEnd arrays? I tried running this code with cow processes that start at the same time and I got the wrong output.
Input:
5
4 10 1
8 13 3
2 6 2
2 4 2
4 7 2
Output:
4