PKU [1089]. Intervals. [TLE].

#include <stdio.h> typedef struct { int initial; int final; } closed_interval; closed_interval input[50000]; int main() { int case_cnt, i, j; int case_max, case_min; scanf("%d", &case_cnt); for(i=0 ; i<case_cnt ; i++) { scanf("%d %d", &input[i].initial, &input[i].final); } for(i=case_cnt ; i>=1 ; i--) { for(j=1 ; j < case_cnt ; j++) { if(input[j-1].initial > input[j].initial) { input[j-1].initial ^= input[j].initial; input[j].initial ^= input[j-1].initial; input[j-1].initial ^= input[j].initial; input[j-1].final ^= input[j].final; input[j].final ^= input[j-1].final; input[j-1].final ^= input[j].final; } } } case_min = input[i].initial; case_max = input[i].final; for(i=0 ; i<=case_cnt ; i++) { if(input[i+1].initial > case_max) { printf("%d %d\n", case_min , case_max); case_min = input[i+1].initial; case_max = input[i+1].final; } else if(input[i+1].final > case_max) { case_max = input[i+1].final; } else { continue; } } printf("%d %d\n", case_min, case_max); return 0; }

In PKU judge system.

허 -_- 간만에 시도해 봤는데... 감이 안돌아왔는지. 해답을 못 찾겠군요 -_-;;
꽤나 자신있게 풀었는데 말이죠. 쩝.

일단 closed_interval 이라는 구조체를 선언하고, 이 구조체를 배열에 저장합니다.
그리고 나서 각 closed interval 의 initial point, final point 를 기록합니다.
이 다음엔 Bubble Sort 로 각 구조체 배열을 정렬하죠.

그 뒤, 우선 제일 첫번째 index 의 initial point, final point 를 각각 case_min, case_max 변수에 저장하고, 각 구간값을 비교해
나갑니다.

next index 의 final 값이 case_max 값보다 크다면 이는 구간의 확장이라 보면 될 것이므로, case_max 값에
next index 의 final 값을 대입하고 다음 루프로 넘어갑니다.

만약 next index 의 initial 값이 case_max 값보다 크다면 interval 이 분할된 것이므로, 현 탐색위치의 initial point, final point를
출력하고, next index 의 탐색을 시작합니다.
탐색시, initial point 와 final point 의 초기화는 당연히 해야 겠죠.

그래서 루프를 나올 때는, 가장 마지막의 initial, final point 역시 출력해 줘야겠죠. -_-...

알고리즘상 문제는 없다고 보여집니다만, TLE 로군요. 다른 방법을 찾아야 하나...





*덧)
차라리 closed interval 을 대수적인 면에서 보기 보단 집합으로 취급하는것도 한 방법일 수 있겠네요.
각 closed interval 의 합집합을 구하면 될 것 같긴 합니다만.

생각 좀 더 해봐야겠네요 -_-;