Help in a DP problem

Question

I'm trying to solve a problem from SPOJ ( link ), which can be briefly described like this: Given n intervals, each with an integer beginning and end, and given the end with max time ( let's call it max_end ) , find in how many ways you can choose a set of intervals that covers 1...max_end. Intervals may overlap. I tried a DP; first sort by end time, then dp[ i ] is a pair, where dp[ i ].first is the minimum number of intervals needed to cover 1...end[ i ] last using interval i and dp[ i ].second is the number of ways to do it. Here's my main DP loop:

for( int i = 1; i < n; i ++ ) {
    for( int j = 0; j < i; j ++ ) {
        if( ! ( x[ j ].end >= x[ i ].start - 1 ) )
            continue;
        if( dp[ j ].first + 1 < dp[ i ].first ) {
            dp[ i ].first = dp[ j ].first + 1;
            dp[ i ].second = dp[ j ].second;
        }
        else if( dp[ j ].first + 1 == dp[ i ].first ) {
            dp[ i ].second += dp[ j ].second;
        }
    }
}

Unfortunately, it didn't work. Can somebody please tell me where I have a mistake? Thanks in advance! :)

Answer 1

I'm not sure I get your solution idea, but I describe my AC solution:

I'm using function with memorization, but you can re-write it using non-recurcive DP.

Let's say we have our intervals in array

pair a[100]; where a[i].first is interval begin and a[i].second is interval end.

Sort this array by begin first (default behavior of stl sort algorithm with default pair comparator).

Now imagine that we are 'putting' intervals one by one from beginning to end.

let f(int x, int prev) return the number of ways to finish the filling if currently last interval is x and previous is 'prev'.

we'll calculate it as follows:

int f(int x, int prev) {
  // if already calculated dp[x][prev], return it. Otherwise, calculate it
  if (dp[x][prev] != -1) {
    return dp[x][prev];
  }
  if (a[x].second == m) {
    return dp[x][prev] = 1; // it means - X is last interval in day
  }
  else {
    dp[x][prev] = 0;
    for (int i = x + 1; i < n; ++i) { // try to select next interval
      if (a[i].first <= a[x].second && // there must be not empty space after x interval
          a[i].second > a[x].second && // if this is false, the set won't be minimal - i interval is useless
          a[i].first > a[x].first && // if this is false, the set won't be minimal, x interval is useless
          a[prev].second < a[i].first) { // if this is false, the set won't be minimal, x interval is useless.  
        dp[x][prev] = (dp[x][prev] + f(i, x)) % 100000000;
      }
    }
  }
  return dp[x][prev];
}

After that we need to call this function for every pair of intervals, first of which start at 0 and second is connected with first:

for (int i = 0; i < n; ++i) {
  if (a[i].first == 0) {
     for (int j = i + 1; j < n; ++j) {
        if (a[j].first > 0 && // we don't need to start at 0 - in this case either i or j will be useless
            a[j].first <= a[i].second && // there must be no space after i interval
            a[j].second > a[i].second) { // in opposite case j will be useless
           res = (res + f(j, i)) % 100000000;
        }
     }
     // also we need to check the case when we use only one interval:
     if (a[i].second == m) {
        res = (res + 1) % 100000000;
     }
  }
}

After that we only need to print the res.