9541번 - 역사 시간 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 128 MB | 58 | 15 | 10 | 29.412% |
문제
현수는 서강대학교에서 한국사를 강의하는 교수이다. 현수는 총 n개의 역사적 사건을 한 수업시간에 하나씩 강의하려고 한다. 이제, 각 강의에 어떤 역사적 사건을 강의할지 결정하려고 한다.
모든 사건은 발생한 특정 구간 [ai, bi]이 있다. 두 사건이 발생한 구간이 겹치는 경우 두 사건을 연관되었다고 한다. 연관된 사건을 최대한 가까운 시간에 강의하면 학생들의 이해도가 높아진다. 또, 연관된 사건이 아닌 경우에는 일어난 순서를 지키면서 강의해야 한다. 즉, A와 B가 연관된 사건이 아니고, A가 B보다 먼저 일어났다면, A는 B보다 먼저 강의해야 한다.
현수가 강의해야 하는 사건의 구간이 모두 주어졌을 때, 두 연관된 사건이 떨어진 거리의 최댓값 k의 최솟값을 구하는 프로그램을 작성하시오. i번째 강의와 j번째 강의 사이의 거리는 |i - j|이다
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 50,000)이 주어진다. 다음 n개 줄에는 사건의 구간 ai와 bi가 주어진다. (-109 ≤ ai ≤ bi ≤ 109) 두 구간이 같은 경우는 없다.
출력
각각의 테스트 케이스 마다, 가장 작은 k를 출력한다. 다음 n개 줄에는 강의 순서를 입력과 같은 형식으로 출력한다.
예제 입력 1
1 3 1 6 2 3 4 5
예제 출력 1
1 2 3 1 6 4 5
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호