Analysis: Goldilocks and the N Cows, by Brian Dean

The process of solving this problem is described in the video above; the final code is shown below.

One small subtlety not discussed in the video above: if there is a tie between two elements -- one from the A array and the other from the B array -- it is important to process the one from the A array first (as we do in our code, since we check if A[i] <= B[j]). This ensures that we get the highest possible milk output at each temperature we consider, by first processing all the cows that become comfortable (entries in the A array), after which we process cows that become too hot (entries in the B array).

The total running time of this solution is O(N log N). The initial sorts run in O(N log N) time, then the ensuing scan through A and B takes only O(N) time.

```#include <iostream>
#include <fstream>
#include <algorithm>
#define MAX_N 20000
using namespace std;

int N, X, Y, Z;
int A[MAX_N+1], B[MAX_N+1];

int main(void)
{
ifstream fin("milktemp.in");
fin >> N >> X >> Y >> Z;
for (int i=0; i<N; i++)
fin >> A[i] >> B[i];
fin.close();

sort(A, A+N);
sort(B, B+N);
A[N] = 1000000001;
B[N] = 1000000001;

// scan through A and B simultaneously
int i=0, j=0;
int current_milk = N*X;
int answer = N*X;
while (i<N || j<N) {
// look at A[i] and B[j].
if (A[i] <= B[j]) {
// next event comes from A array
current_milk += Y-X;
i++;
} else {
// next event comes from B array
current_milk += Z-Y;
j++;
}
if (current_milk > answer)