Analysis: Recording the Moolympics by Mark Gordon

When you can only record one program at a time this problem is relatively straightforward. The next program you should record is always the program that ends soonest and has not yet started. Unfortunately, if you use this approach to schedule the first tape and then again (after removing those programs already recorded) to schedule the second tape you may not be able to schedule everything you want. The simplest test case that demonstrates this is illustrated below.

Track 1 : |-| |-| |---------|
Track 2 : |---------| |-| |-|

If you put all of the small programs on the same track it becomes impossible to schedule the larger program. So an alternate approach is needed.

One approach is to use dynamic programming. Our state can be described as the last two programs that were recorded on each track. We can attempt to put any program that starts later than those two programs on either track if it starts after the current program on that track ends.

It is important, however, that we restrict to only programs that start after the last recorded programs on each track. Otherwise we may attempt to record the same program on both tracks which would incorrectly inflate the answer.

Alternatively, there is a more efficient greedy algorithm that does correctly solve this problem. The algorithm works by considering programs in order of ascending end times, tracking what the last two programs recorded on each track were. If the program starts before either track's program finishes then the program cannot be scheduled. If it fits on only one track it should be scheduled there. Otherwise the program should be greedily scheduled on the track with the later ending current program.

This approach is based on the idea that, considering the programs in this order, we should always assign a program to a track if we can. This is because all later tracks we will consider have a later start time and therefore further constrain the track. In the case that the program can fit on either track we should assign to the track which already has the later ending program. This may allow us to assign tracks that start earlier (and end later) in the future.

Below is my solution implementing the dynamic programming algorithm.

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>

using namespace std;

#define MAXN 160

int N;
int A[MAXN];
int B[MAXN];

int memo[MAXN][MAXN];

int solve(int x, int y) {
  if(B[y] < B[x]) return solve(y, x);

  int& ref = memo[x][y];
  if(ref != -1) return ref;

  ref = 0;
  for(int i = 0; i < N; i++) {
    if(B[x] <= A[i] && i != y) {
      ref = max(ref, 1 + solve(i, y));
    }
  }

  return ref;
}

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

  cin >> N;
  assert(1 <= N && N <= 150);
  for(int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
  }
  A[N] = B[N] = 0;

  memset(memo, -1, sizeof(memo));
  cout << solve(N, N) << endl;
  return 0;
}

And this is Vickie Wang's O(N log N) greedy solution.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int> > slot;
int N;

int main() {
   freopen("recording.in", "r", stdin);
   freopen("recording.out", "w", stdout);
   scanf("%d", &N);
   for(int i = 0; i < N; ++i) {
       int a, b;
       scanf("%d %d", &a, &b);
       slot.push_back(make_pair(b,a));
   }
   sort(slot.begin(), slot.end());
   
   int cnt = 0;
   int t1(0), t2(0);
   for(int i = 0; i < N; ++i) {
       int checka = slot[i].second;
       if(checka < t1) {
           continue;
       } else if(checka < t2) {
           t1 = t2;
           t2 = slot[i].first;
           ++cnt;
       } else {
           t2 = slot[i].first;
           ++cnt;
       }
   }
   printf("%d\n", cnt);
   return 0;
}