PKU 1089. Intervals. [판정:TLE]

나름 자료구조를 배웠다고 써먹어볼려고는 하는데

좀 쓸모가 있어야지 써먹든가 하지요 -_-

#include <iostream> using namespace std; class interval { public: int lb; // lower bound int ub; // upper bound interval *prev; interval *next; interval(); }; interval::interval() { lb = 0; ub = 0; prev = NULL; next = NULL; } class ilist { public: interval *head; interval *tail; int count; ilist(); int size(); bool insertLast( int a, int b ); interval* popFirst(); void iswap( interval *ix, interval *iy ); void selectionSort(); }; ilist::ilist() { head = NULL; tail = NULL; count = 0; } int ilist::size() { return count; } bool ilist::insertLast( int a, int b ) { int intersect = 0; interval *walker; walker = this->head; while( walker != NULL ) { if( a <= walker->lb && walker->lb <= b ) { intersect = 1; walker->lb = a; } if( a <= walker->ub && walker->ub <= b ) { intersect = 1; walker->ub = b; } walker = walker->next; } if( intersect ) { return false; } else { interval *fresh = new interval; fresh->lb = a; fresh->ub = b; fresh->prev = this->tail; if( size() == 0 ) { this->head = fresh; this->tail = fresh; } else { fresh->prev->next = fresh; this->tail = fresh; } count++; return true; } } interval* ilist::popFirst() { if( size() == 0 ) { return NULL; } else { interval *temp = this->head; this->head = temp->next; temp->next = NULL; if( this->head != NULL ) this->head->prev = NULL; if( size() == 1 ) this->tail = NULL; count--; return temp; } } void ilist::iswap( interval *ix, interval *iy ) { swap( ix->lb, iy->lb ); swap( ix->ub, iy->ub ); } void ilist::selectionSort() { int i; int j; int n; interval *kthFront; interval *minpos; int min; interval *walker; n = this->size(); for( i = 0; i < n-1; i++ ) { kthFront = this->head; for( j = 0; j < i; j++ ) { kthFront = kthFront->next; } minpos = kthFront; min = minpos->lb; walker = kthFront; while( walker != NULL ) { if( min > walker->lb ) { min = walker->lb; minpos = walker; } walker = walker->next; } if( minpos != kthFront ) { iswap( minpos, kthFront ); } } } int main() { int n; int low; int up; ilist ins; // ins : INtervalS interval *temp; int i; cin >> n; while( n > 0 ) { cin >> low >> up; if( low <= up ) { bool judge = ins.insertLast( low, up ); i = 0; while( !judge || i < ins.size() ) { temp = ins.popFirst(); low = temp->lb; up = temp->ub; delete temp; judge = ins.insertLast( low, up ); i++; } } n--; } ins.selectionSort(); while( temp = ins.popFirst() ) { cout << temp->lb << " " << temp->ub << endl; delete temp; } return 0; }

대충 계산해본 바로는

탐색에만 최대 O(4N²)을 소비하는 것 같으니 난감할 뿐 ㅋㅋㅋ

일단 TLE받은 것도 있고,

지금 바쁜것도 있고 하니 설명은 나중에 쓰거나 안쓰거나 할 예정입니다

조만간 배열로 다시 풀어서 제출할 예정이라는 -_-;

ps. Dlbo군은 또 정신놓고 이거 발행하는 짓은 하지 말기를 -_-a