시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 777 | 328 | 226 | 38.370% |
상근이는 올림픽을 매우 좋아하면서 싫어한다. 올림픽을 좋아하는 이유는 많은 스포츠 경기를 볼 수 있기 때문이고, 싫어하는 이유는 경기가 동시에 열리기 때문이다.
방금 올림픽이 열리는 장소에 도착을 했다. 하지만, 경기가 동시에 열리기 때문에, 상근이는 모든 경기를 실시간으로 볼 수 없다.
모든 경기의 시작 시간과 종료 시간, 그리고 날짜가 주어진다. 이때, 상근이가 볼 수 있는 경기의 최대 개수를 구하는 프로그램을 작성하시오. 상근이는 경기장에 시작 시간에 들어가며, 종료 시간에 나오게된다. 한 경기를 보던 중에 다른 경기를 보기 위해 경기장을 옮길 수 없다. 또, 경기장을 이동하는데 걸리는 시간은 없다. 마지막으로, 경기가 시작된 이후에는 경기장에 들어갈 수 없다.
입력의 첫째 줄에는 테스트 케이스의 개수 n이 주어진다.
각 테스트 케이스의 첫째 줄에는 경기의 수 1 ≤ m ≤ 50000 이 주어진다. 다음 m개 줄에는 각 경기의 정보를 나타내는 세 정수 d, s, e가 주어진다. d는 경기의 날짜, s는 시작 시간, e는 종료 시간을 나타낸다. 시간은 hhmm형식으로 주어지며, 모든 경기는 시작한 날에 끝난다.
각 테스트 케이스마다 "Scenario #i:"를 출력한다. 여기서 i는 테스트 케이스 번호이며 1부터 시작한다. 그 다음 줄에는 상근이가 참석할 수 있는 경기의 최대 개수를 출력한다. 문제에서도 설명했지만, 경기장을 이동하는데 걸리는 시간은 없다. 즉, 경기 A의 종료 시간이 B의 시작 시간과 같은 경우에 상근이는 A 이후에 바로 B로 이동할 수 있다. 각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.
2 10 1 1220 1340 2 1155 1220 2 1220 1340 3 1220 1240 1 1200 1320 2 1250 1310 2 1330 1550 3 1030 1130 3 1130 1300 3 1240 1330 3 1 0500 2200 1 0000 0700 1 2000 2359
Scenario #1: 7 Scenario #2: 2