주차 구역 예약 점검

문제

주차장 예약 서비스를 담당하는 백엔드 개발자는 하루 동안 접수된 예약을 점검하려 한다. 이 주차장에는 번호가 붙은 여러 주차 구역이 있으며, 한 구역에는 동시에 한 대의 차량만 주차할 수 있다. 예약 데이터에는 주차 구역 번호, 이용 시작 시각, 이용 종료 시각이 기록되어 있다. 모든 시각은 점검 대상 날짜의 자정부터 지난 분으로 표현한다. 예약의 이용 구간은 시작 시각을 포함하고 종료 시각을 포함하지 않는다. 따라서 한 예약이 끝나는 시각에 다른 예약이 시작하면 두 예약은 충돌하지 않는다. 반면 같은 구역에 배정된 두 예약의 이용 구간이 조금이라도 겹치면 두 예약은 충돌한다. 서로 다른 구역의 예약은 이용 시각이 같더라도 충돌하지 않는다. 모든 예약은 시작 시각보다 종료 시각이 크므로 길이가 0인 예약은 없다. 점검 프로그램은 충돌하는 예약 쌍의 개수가 아니라, 충돌이 한 번 이상 발생하는 주차 구역의 개수를 구해야 한다. 같은 구역에서 여러 예약이 연속으로 겹치거나 하나의 긴 예약 안에 여러 짧은 예약이 들어 있어도 그 구역은 한 번만 센다. 구역 번호와 이용 구간이 모두 같은 예약이 여러 줄에 나타나면 각각 별개의 예약으로 취급하므로, 이 예약들 사이에도 충돌이 발생한다. 입력 기록은 접수 순서로 저장되어 있으며 구역 번호나 시각 순서로 정렬되어 있다는 보장은 없다. 예약을 취소하거나 이용 구간을 바꾸지 않고, 주어진 기록 자체에서 충돌 여부를 판단한다. 충돌이 발생한 구역의 개수와 그중 가장 작은 구역 번호를 출력하는 프로그램을 작성한다. 충돌이 발생한 구역이 하나도 없으면 개수는 0, 구역 번호는 -1로 출력한다.

입력

첫째 줄에 예약 수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
다음 N개 줄에는 주차 구역 번호 P, 시작 시각 S, 종료 시각 E가 공백으로 구분되어 주어진다. 1 ≤ P ≤ 1,000이고 0 ≤ S < E ≤ 1,440이다.
입력에 등장하는 모든 수는 정수이다.

출력

충돌이 발생한 서로 다른 구역의 개수와 그중 가장 작은 구역 번호를 공백으로 구분하여 한 줄에 출력한다. 충돌이 없으면 0 -1을 출력한다.

6
4 30 80
2 0 20
4 70 90
2 20 40
7 100 200
7 120 130

2 4

4
3 0 10
3 10 20
8 5 15
3 20 30

0 -1

3
9 10 20
9 10 20
9 15 25

1 9

출처: Devin.KR 자체 제작