7888번 - 두 교수 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 144 | 14 | 14 | 30.435% |
문제
알고스팟 대학교에는 서로를 정말 싫어하는 교수 두 명이 있다. 이 대학교에서는 교수의 이름을 숫자로 부른다. 서로 싫어하는 두 교수의 번호는 1과 2이다.
알고스팟 대학교에는 총 n명의 교수가 있고, 수업은 매일 매일 같은 시간에 진행된다. 각 교수가 맡은 수업은 하나이다. 모든 수업의 시작 시간과 종료 시간은 정해져있다. 또, 수업을 조금 더 늦게 끝내거나, 일찍 시작하는 것은 불가능하다. 학교에서 정한 수업 이외의 수업은 할 수 없다.
아직 학교는 수업의 강의실을 정해놓지 않았다. 시간이 겹치는 수업은 같은 강의실에 배정할 수 없다. 하지만, 끝 시간과 시작 시간이 같은 두 수업은 같은 강의실에 배정할 수 있다. 모든 수업에 강의실을 배정할 때, 필요한 강의실의 최소 개수를 구하는 프로그램을 작성하시오. 1번 교수와 2번 교수는 서로를 매우 싫어하기 때문에, 같은 강의실에서 수업을 진행하지 않는다.
입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 250) 각 테스트 케이스의 첫째 줄에는 교수의 수 n (2 ≤ n ≤ 105)이 주어진다. 다음 n개 줄에는 i번 교수가 맡은 수업의 시작 시간 starti와 끝 시간 endi가 주어진다. (0 ≤ starti < endi ≤ 109) 입력의 크기는 50MB를 넘지 않는다.
출력
모든 수업에 강의실을 배정하는데 필요한 강의실의 최소 개수를 출력한다.
예제 입력 1
4 2 0 10 10 20 3 0 10 10 20 10 20 5 4 14 3 13 2 12 1 11 0 10 4 0 10 10 20 20 30 30 40
예제 출력 1
2 2 5 2
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호