Analysis: Photo by Mark Gordon

In this problem we're given intervals of cows that each contain exactly one spotted cow and we're asked what is the maximum number of spotted cows that can be present.

This can be solved by formulating the problem as a dynamic programming problem. Suppose we decide which cows are spotted from left to right. The next cow that is made spotted doesn't break the interval constraints if and only if it creates no empty intervals between it and the previous spotted cow and is not contained in any of the same intervals as the previous spotted cow.

Therefore the position of the last spotted cow can be used for a dynamic programming solution. Let DP[x] give the number of spotted cows that can be placed after (and including) position x if a spotted cow must be placed at position x. All intervals ending after position x must be satisfied. We can place the next spotted cow at any position such that there are no empty intervals between it and x and that no interval contains both it and x. So we can write

DP[x] = 1 + max{DP[i] : max{b_j : a_j <= x} < i <= min{b_j : x < a_j}}

If there are no i satisfying max{b_j : a_j <= x} < i <= min{b_j : x < a_j} then a spotted cow cannot be placed at position x. The overall result of the algorithm can be considered the value of DP[0] - 1 (a position to the left of everything not contained in any intervals).

This leads directly to an O(N^2) algorithm. To speed this up note that we can precompute max{b_j : a_j <= x} and min{b_j : x < a_j} in O(N) time to get constant time queries. This is just transforming an array into the max of its prefixes and min of its suffixes. Then a tree, a segment tree or Fenwick tree will do nicely, can be used to compute the maximum DP value in the range.

Alternatively, taking advantage of the monotonic nature of the query ranges, a max queue can be used to make the entire algorithm run in O(N) time. The O(N) algorithm is demonstrated below:

#define MAXN 200010

int DP[MAXN];
int RMN[MAXN];
int RMX[MAXN];

template <class T>
struct max_queue {
  explicit max_queue(size_t sz) : X(sz), Y(sz), a(0), b(0), va(0), vb(0) {
  }

  void push(const T& v) {
    while(va < vb && X[vb - 1] <= v) vb--;
    X[vb] = v;
    Y[vb++] = b++;
  }

  void pop() {
    va += a++ == Y[va];
  }

  T max() {
    return X[va];
  }

  vector<T> X;
  vector<size_t> Y;
  size_t a, b, va, vb;
};

int main() {
  freopen("photo.in", "r", stdin);
  freopen("photo.out", "w", stdout);

  int N, M; scanf("%d%d", &N, &M);
  fill(RMN, RMN + N + 1, N + 2);
  for(int i = 0; i < M; i++) {
    int lft, rht; scanf("%d%d", &lft, &rht);
    RMN[lft] = min(RMN[lft], rht + 1);
    RMX[lft] = max(RMX[lft], rht + 1);
  }

  /* Precompute the DP query ranges. */
  RMN[N + 1] = N + 2;
  for(int i = N - 1; i >= 0; i--) {
    RMN[i] = min(RMN[i], RMN[i + 1]);
  }
  for(int i = 1; i <= N; i++) {
    RMX[i] = max(RMX[i], RMX[i - 1]);
  }
  DP[N + 1] = 0;

  int j_lo = N;
  int j_hi = N;
  max_queue<int> mq(N);
  for(int i = N; i >= 0; i--) {
    /* Calcualte the DP range interval. */
    int r_least = max(i + 1, RMX[i]);
    int r_most = RMN[i + 1];

    /* Push newly accessible DP values. */
    for(; r_least <= j_lo; j_lo--) {
      mq.push(DP[j_lo]);
    }

    /* Pop no longoer accessible DP values. */
    for(; j_lo < j_hi && r_most <= j_hi; j_hi--) {
      mq.pop();
    }

    /* Compute the maximum reachable substate.  If nothing is reachable the
     * value for this state is -1.  If we're not at the beginning and it's not
     * impossible to place a cow here increment by 1. */
    DP[i] = r_least < r_most ? mq.max() : -1;
    if(i && DP[i] != -1) {
      DP[i]++;
    }
  }

  printf("%d\n", DP[0]);
  return 0;
}