(Analysis by Nick Wu)

In this problem we're given a list of the types of milk that each guest drank, when they drank each type, and when/if they got sick. Using this information we want to determine how many people may become sick given that exactly one type of milk is bad and making people sick.

To solve this problem we want to identify which types of milk could be the bad milk. We are explicitly told that a type of milk can be bad if, for every person that got sick, each person drank that type of milk before they got sick. Therefore, we loop over each sick person and ensure that they drank the candidate type of milk prior to getting sick.

Then to find the maximum number of guests who could become sick we want to find the maximum number of people who drank one of these candidate bad milks.

Here is my code documenting the given solution:

import java.io.*;
import java.util.*;
/*
* For record i of a person drinking milk, we store data as follows:
* personDrink[i]: the person who drank the milk
* milkDrink[i]: the type of milk that the person drank
* timeDrink[i]: the time the person drank the milk
*/
static int[] personDrink;
static int[] milkDrink;
static int[] timeDrink;

/*
* For record i of a person being sick, we store data as follows:
* personSick[i]: the person who got sick
* timeSick[i]: the time that person got sick
*/
static int[] personSick;
static int[] timeSick;

public static void main(String[] args) throws IOException {
// initialize file I/O
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("badmilk.out")));

// read in the first line, store n, m, d, and s
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());

// initialize the arrays about drinking milk
personDrink = new int[d];
milkDrink = new int[d];
timeDrink = new int[d];
for(int i = 0; i < d; i++) {
// read in record i of someone drinking milk
personDrink[i] = Integer.parseInt(st.nextToken());
milkDrink[i] = Integer.parseInt(st.nextToken());
timeDrink[i] = Integer.parseInt(st.nextToken());
}

// initialize the arrays about people getting sick
personSick = new int[s];
timeSick = new int[s];
for(int i = 0; i < s; i++) {
// read in record i of someone drinking
personSick[i] = Integer.parseInt(st.nextToken());
timeSick[i] = Integer.parseInt(st.nextToken());
}

int maxCanGetSick = 0;

for(int i = 1; i <= m; i++) {
// check if milk type i can be bad
// the milk type can be bad, now count how many people drank that type of milk
int numDrank = numPeopleDrink(i);
if(numDrank > maxCanGetSick) {
// update the maximum number of people that could be sick
maxCanGetSick = numDrank;
}
}
}

pw.println(maxCanGetSick);

// close output stream
pw.close();
}

/*
* Given a type of milk, this method returns true if and only if
* the given milk type could be bad. This is true if and only if
* for each person who got sick, this person consumed the given
* type of milk before that person got sick.
*/
private static boolean milkTypeCanBeBad(int milkType) {
// loop over all records of people being sick
for(int i = 0; i < personSick.length; i++) {
// check for record i of sickness if that person drank that milk before they got sick
if(!personDrankMilkBefore(personSick[i], milkType, timeSick[i])) {
// that person did not, this milk type cannot be bad then
return false;
}
}
// all the records checked out, so return true
return true;
}

/*
* Given a person, a type of milk, and a time, this method returns
* true if and only if the given person drank the given type of milk
* before the given time.
*/
private static boolean personDrankMilkBefore(int person, int milkType, int time) {
// loop over all records of drinking
for(int i = 0; i < personDrink.length; i++) {
// check if record i of drinking if that person did drink that type of milk before the given time
if(personDrink[i] == person && milkDrink[i] == milkType && timeDrink[i] < time) {
// all conditions are satisfised, return true
return true;
}
}
// none of the records satisfied the conditions, return false
return false;
}

private static int numPeopleDrink(int milkType) {
// didDrink[i] will be true if and only if person i did drink the given type of milk
boolean[] didDrink = new boolean[51];
// loop over all records of drinking
for(int i = 0; i < personDrink.length; i++) {
// check if this record corresponds to the given type of milk
if(milkDrink[i] == milkType) {
// it does, mark that this person did drink that milk
didDrink[personDrink[i]] = true;
}
}
// now that we've looped over all records, just count the number of people
// who drank that milk
int numPeopleDrink = 0;
for(int i = 1; i < didDrink.length; i++) {
if(didDrink[i]) {
numPeopleDrink++;
}
}
return numPeopleDrink;
}

}