PKU 1089. Intervals. [판정:WA]

알고리즘을 약간 수정해서 TLE는 빠져나왔지만 WA군요

어디가 틀린건지 -_-;

#include <stdio.h> #include <stdlib.h> typedef struct interval { int lb; // lower bound int ub; // upper bound struct interval *prev; struct interval *next; } interval; typedef struct ilist { interval *head; interval *tail; int count; } ilist; void listinit( ilist *il ); int size( ilist *il ); interval* popFirst( ilist *il ); void iswap( interval *ix, interval *iy ); void insertLast( ilist *il, int a, int b ); void selectionSort( ilist *il ); void main() { int n; int low; int up; ilist ins; // ins : INtervalS interval *temp; listinit(&ins); scanf("%d", &n); while( n > 0 ) { scanf("%d %d", &low, &up); if( low <= up ) { insertLast( &ins, low, up ); } n--; } selectionSort(&ins); while( temp = popFirst(&ins) ) { printf("%d %d\n", temp->lb, temp->ub); free( temp ); } } void listinit( ilist *il ) { il->head = NULL; il->tail = NULL; il->count = 0; } int size( ilist *il ) { return il->count; } interval* popFirst( ilist *il ) { if( size(il) == 0 ) { return NULL; } else { interval *temp = il->head; il->head = temp->next; temp->next = NULL; if( il->head != NULL ) il->head->prev = NULL; if( size(il) == 1 ) il->tail = NULL; il->count--; return temp; } } void iswap( interval *ix, interval *iy ) { int temp; // swap( ix->lb, iy->lb ) temp = ix->lb; ix->lb = iy->lb; iy->lb = temp; // swap( ix->ub, iy->ub ) temp = ix->ub; ix->ub = iy->ub; iy->ub = temp; } void insertLast( ilist *il, int a, int b ) { int intersect = 0; interval *walker; interval *temp; walker = il->head; while( walker != NULL ) { if( (a - walker->ub)*(b - walker->lb) <= 0 ) { intersect = 1; } if( a <= walker->lb && walker->lb <= b ) { walker->lb = a; } if( a <= walker->ub && walker->ub <= b ) { walker->ub = b; } if( intersect ) { a = walker->lb; b = walker->ub; if( walker != il->head ) iswap( walker, il->head ); temp = popFirst(il); free( temp ); walker = il->head; intersect = 0; } else { walker = walker->next; } } if( !intersect ) { interval *fresh = ( interval* )malloc( sizeof( interval ) ); fresh->lb = a; fresh->ub = b; fresh->prev = il->tail; fresh->next = NULL; if( size(il) == 0 ) { il->head = fresh; il->tail = fresh; } else { fresh->prev->next = fresh; il->tail = fresh; } il->count++; } } void selectionSort( ilist *il ) { int i; int j; int n; interval *kthFront; interval *minpos; int min; interval *walker; n = size(il); for( i = 0; i < n-1; i++ ) { kthFront = il->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 ); } } }