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) 
      answer = current_milk;
  }

  ofstream fout("milktemp.out");
  fout << answer << "\n";
  fout.close();

  return 0;
}