USACO 1.2 Milking Cows

Simple brutal force search with intervals.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Interval {
  int start, end;
  Interval(int start, int end) : start(start), end(end) {}
  bool operator < (const Interval& interval) const {
    return start < interval.start;
  }
};

int main () {
  string str;
  ifstream fin ("milk2.in");
  ofstream fout ("milk2.out");

  vector<Interval> intervals;

  int farmers;
  fin >> farmers;
  for (int i = 0; i < farmers; ++i) {
    int start, end;
    fin >> start >> end;
    intervals.emplace_back(Interval(start, end));
  }

  std::sort(intervals.begin(), intervals.end());

  int maxOverlap = 0, maxGap = 0;
  Interval it = intervals[0];
  for (int i = 1; i < intervals.size(); ++i) {
    if (intervals[i].start > it.end) {
      // none overlap
      maxOverlap = std::max(maxOverlap, it.end - it.start);
      maxGap = std::max(maxGap, intervals[i].start - it.end);
      it = intervals[i];
    } else {
      it.end = std::max(it.end, intervals[i].end);
    }
  }

  maxOverlap = std::max(maxOverlap, it.end - it.start);

  fout << maxOverlap << " " << maxGap << std::endl;

  return 0;
}