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