Interval Time Schedulingを動的計画法を「使わないで」解く

C++のリハビリ代わりに、とか思ったらまじ忘れまくってるし。cout.hはTZTester をどうにかするブーム - naoya_t@topcoder - TopCoder部より。

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include "cout.h"

using namespace std;

class TimeInteval {
private:
  int s;
  int f;
  int weight;
public:
  TimeInteval( int s, int f, int weight ) {
	this->s = s;
	this->f = f;
	this->weight = weight;
  };

  ~TimeInteval() {
  };

  int getStart() {
	return s;
  }
  
  int getFinish() {
	return f;
  }
  
  int getWeight() {
	return weight;
  }

};

ostream& operator<<( ostream& os, TimeInteval t) {
  os << "( Start: " << t.getStart() 
	   << ", Finish: " << t.getFinish() 
	 << ", Weight " << t.getWeight() << " )";
  return os;
}

bool compare( TimeInteval* a, TimeInteval* b ) { 
  return ( (*a).getFinish() < (*b).getFinish() );
}

TimeInteval* p(TimeInteval* t, vector<TimeInteval*> tiv){
  // tの終点fと交差しない最大のTtの終点fと交差しない最大のTimeIntevalを返す
  sort(tiv.begin(), tiv.end(), compare);
  reverse(tiv.begin(), tiv.end()); // 大きい順に見ていく
  for (vector<TimeInteval*>::iterator it = tiv.begin(); it != tiv.end(); ++it) {
	if ( (*t).getStart() > (**it).getFinish() ) {
	  return *it;
	}
  }
  return NULL;
}

vector<TimeInteval*> maximumInternal(vector<TimeInteval*>v, TimeInteval* tail, vector<TimeInteval*> result) {
  if(p(tail, v) == NULL) {
	return result;
  }
  vector<TimeInteval*> tmp;
  TimeInteval* lastValue;
  for (vector<TimeInteval*>::iterator it = v.begin(); it != v.end(); ++it) {
	if( (**it).getFinish() < (*tail).getStart() ) {
	  tmp.push_back(*it);
	  lastValue = *it;
	}
  }
  result.push_back(lastValue);
  return maximumInternal(tmp, lastValue, result);
}

vector<TimeInteval*> maximum(vector<TimeInteval*> v) {
  // 再帰で見ていく
  vector<TimeInteval*> result;
  TimeInteval* tail;
  sort(v.begin(), v.end(), compare);
  for (vector<TimeInteval*>::iterator it = v.begin(); it != v.end(); ++it) {
	tail = *it;
  }
  result.push_back(tail);
  return maximumInternal(v, tail, result);
}


int main (int argc, char **argv) 
{
  
  vector<TimeInteval*> v;

  TimeInteval* t1 = new TimeInteval(1, 3, 1);
  v.push_back(t1);
  TimeInteval* t2 = new TimeInteval(4, 5, 2);
  v.push_back(t2);
  TimeInteval* t3 = new TimeInteval(3, 4, 2);
  v.push_back(t3);
  TimeInteval* t4 = new TimeInteval(7, 10, 2);
  v.push_back(t4);
  TimeInteval* t5 = new TimeInteval(6, 9, 2);
  v.push_back(t5);
  TimeInteval* t6 = new TimeInteval(7, 12, 2);
  v.push_back(t6);
  TimeInteval* t7 = new TimeInteval(10, 11, 2);
  v.push_back(t7);
  TimeInteval* t8 = new TimeInteval(2, 10, 2);
  v.push_back(t8);
  TimeInteval* t9 = new TimeInteval(12, 20, 2);
  v.push_back(t9);

  sort(v.begin(), v.end(), compare);

  cout << "Time inteval list is as follows." << endl;
  for (vector<TimeInteval*>::iterator it = v.begin(); it != v.end(); ++it) {
	cout << **it << endl;
  }

  cout << *p(t2, v) << endl;
  cout << *p(t4, v) << endl;

  vector<TimeInteval*> result = maximum(v);
  sort(result.begin(), result.end(), compare);

  int cnt = result.size();
  cout << "[ ";

  for (int i = 0; i < cnt; ++i) {
	if (i > 0) cout << ", ";
	cout << *(result[i]);
  }
  cout << " ]" << endl;

  return 0;
}

実行結果。

/Users/syou6162/cpp% g++ -Wall time_interval_scheduling.cpp
/Users/syou6162/cpp% ./a.out
Time inteval list is as follows.
( Start: 1, Finish: 3, Weight 1 )
( Start: 3, Finish: 4, Weight 2 )
( Start: 4, Finish: 5, Weight 2 )
( Start: 6, Finish: 9, Weight 2 )
( Start: 7, Finish: 10, Weight 2 )
( Start: 2, Finish: 10, Weight 2 )
( Start: 10, Finish: 11, Weight 2 )
( Start: 7, Finish: 12, Weight 2 )
( Start: 12, Finish: 20, Weight 2 )
( Start: 1, Finish: 3, Weight 1 )
( Start: 4, Finish: 5, Weight 2 )
[ ( Start: 1, Finish: 3, Weight 1 ), ( Start: 4, Finish: 5, Weight 2 ), ( Start: 6, Finish: 9, Weight 2 ), ( Start: 10, Finish: 11, Weight 2 ), ( Start: 12, Finish: 20, Weight 2 ) ]