USACO DEC09 Problem 'sgraze' Analysis

by Neal Wu

First, sort all cow ranges by their ending points. Then for each k from 0 to N, compute dp [k], which is the largest number of the first k cows that can graze without any overlapping ranges. Thus, when computing dp [i + 1], if j is the largest index of any cow satisfying cow [j].end <= cow [i].start, we have the following recurrence:

dp [i + 1] = max (dp [j] + 1, dp [i]).

We can compute j with binary search in O(log N) time for each i, and thus the algorithm is O(N log N) overall.

#include <cstdio>
#include <algorithm>
using namespace std;

FILE *fin = fopen ("sgraze.in", "r"), *fout = fopen ("sgraze.out", "w");

const int MAXN = 50005;

struct range {
    int start, end;

    inline bool operator < (const range &o) const {
        return end < o.end;
    }
};

int N, dp [MAXN];
range cows [MAXN];

inline int find (int last) {
    int lo = -1, hi = N - 1, mid;

    while (lo < hi) {
        mid = (lo + hi + 1) / 2;
        if (cows [mid].end <= last) lo = mid;
        else                           hi = mid - 1;
    }
    return lo + 1;
}

int main () {
    fscanf (fin, "%d", &N);

    for (int i = 0; i < N; i++)
        fscanf (fin, "%d %d", &cows [i].start, &cows [i].end);

    sort (cows, cows + N);

    for (int i = dp [0] = 0; i < N; i++)
        dp [i + 1] = max (dp [find (cows [i].start)] + 1, dp [i]);

    fprintf (fout, "%d\n", dp [N]);
    return 0;
}