# 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 ) ]
```