PKU 1089. Intervals. AC get.... -_-;

#include <iostream> #include <cstdio> #include <cstdlib> using namespace std; typedef struct { int start, end; }dis; int cmp(const void * a, const void * b) { dis * first = (dis *)a; dis * second = (dis *)b; if (first->start == second->start) { return first->end - second->end; } return first->start - second->start; } dis list[50000]; int main() { int n, i, min, max; cin >> n; i = 0; while(i < n) { scanf("%d%d", &(list[i].start), &(list[i].end)); i++; } qsort(list, n, sizeof(list[0]), cmp); min = list[0].start; max = list[0].end; for (i = 1; i < n; i++) { if (list[i].start > max) { printf("%d %d\n", min, max); min = list[i].start; max = list[i].end; } if (list[i].end > max) { max = list[i].end; } } printf("%d %d\n", min, max); }

제길.

제가 싫어하는 문제의 아주 전형적인 형태였군요.

바로 금방 전 띄운 포스트에서 WA만이 문제가 아니었습니다.

cin과 cout으로 인해 WA를 피하더라도 TL이 걸릴 수 밖에 없더군요.

아시는 분은 아시겠지만 cin과 cout는 지나치게 느린 면이 있습니다.

이렇게 각 언어의 고유성을 무시하게 만드는 문제는 별로 안좋아합니다 -_-;

이 알고리즘은 바로 직전 포스트에 띄운 마지막 P.S 부분에 휘갈긴 알고리즘입니다.

일단 퀵소트로 정렬하고,

min값과 max값을 설정합니다.

만약

5 6
1 4
10 10
6 9
8 10

이리 입력했다면

1 4
5 6
6 9
8 10
10 10

이리 들어가는거지요.

이후 min과 max가 1, 4가 되고,

max보다 시작점이 커지는 경우까지 max값을 갱신하면서

(max값이 시작점보다 작은데 끝점이 max보다 크면 max 갱신, 아니면 무시)

루프를 돌다, max보다 시작점이 커지면 min과 max를 출력합니다.

이 예제에선 1과 4, 첫줄에서 끝나네요.

이후 min = 5, max = 6이 됩니다.

다시 같은 루프를 반복해 돌면서 min = 5, max = 10으로 루프의 마지막까지 돌게 되고,

루프 탈출 직후 이를 출력해 줍니다.

바로 답이 나오지요.

-_-...;;

정확한 알고리즘의 시간도는 O(nlogn + n)이 되는군요.

여전히 이전 포스트에 띄운 알고리즘의 문제점을 발견하시는 분은 댓글 달아주시길 기다리고 있습니다;

P.S.

Mr.K.

매트릭스 풀이 태클 아직 안들어오네 ㅡ,.ㅡ;