문제1084--집중근무시간

1084: 집중근무시간

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

부잣집 도시개 프로도, 카카오에 취직하다!

어느덧 졸업을 하고 취업을 하게 된 프로도.

업무 강도가 빡세기로 유명한 카카오 멀티미디어처리파트에 입사를 하게 된다!

부잣집에서 태어난 프로도에게 회사는 그저 취미로 다닐 뿐. 업무는 대충대충하며 여자친구 네오와 카톡질을 일삼자 이를 보다 못해 분노한 멘토 제시, 파트장 콜린, 팀장 러셀은 돌아가며 프로도 자리를 순찰하기로 결심한다.

한 번만 더 걸리면 짤릴 것이 분명하기에 프로도는 당신에게 집중근무시간을 계산하는 프로그램을 의뢰하였다. 순찰 시작/종료 시간 리스트가 주어지면 겹치는 구간을 병합하여 최종적으로 집중 근무해야 할 시간의 시작/종료 구간들의 리스트를 반환하는 프로그램을 작성하라.

예를 들어 제시, 콜린, 러셀의 순찰 시간이 각각 [1, 3], [6, 8], [2, 5] 라면

1

2

3

4

5

6

7

8

제시

O

O

O

콜린

O

O

O

러셀

O

O

O

O

[1, 5] [6, 8] 시간에는 집중 근무를 해야 한다.


입력 설명

첫 줄에는 테스트 케이스 개수 T(1<= T <= 50) 가 주어진다.

각 테스트 케이스 별로,

구간의 개수 N (1 <= N <= 1000) 이 주어지고,

다음 줄에는 2*N 개의 순찰 시작, 종료 시간이 순서대로 주어진다 (0 <= 시간 <= 1,000,000,000)

출력 설명

각 테스트 케이스 별로 집중 근무시간 구간의 개수를 출력한 후,

다음 줄에는 구간의 시작, 종료 시간을 나열한다.

이 때, 구간의 시작 시간을 기준으로 오름차순으로 나열한다.

입력 예시 Copy

2
3
1 3 6 8 2 5
3
1 2 4 7 1 6

출력 예시 Copy

2
1 5 6 8
1
1 7