게임 서버 예약 충돌 목록

문제

게임 서버 운영팀은 여러 서버의 점검과 시험 경기 일정을 하나의 예약 목록으로 관리한다. 백엔드 담당자는 목록을 배포하기 전에 같은 서버에 시간이 겹치는 예약이 있는지 검사해야 한다. 각 예약에는 사용할 서버 번호, 시작 시각, 종료 시각이 기록되어 있으며, 입력된 순서대로 1번부터 N번까지 예약 번호를 붙인다. 서로 다른 예약이 완전히 같은 내용을 가질 수도 있으며, 이때도 별개의 예약으로 취급한다. 예약은 시작 시각부터 서버를 사용하고 종료 시각에는 서버를 반환한다. 즉, 시작 시각이 S이고 종료 시각이 E인 예약의 사용 구간은 S 이상 E 미만이다. 따라서 한 예약의 종료 시각과 다른 예약의 시작 시각이 같으면 두 예약은 충돌하지 않는다. 서로 다른 서버를 사용하는 예약은 시간이 겹쳐도 충돌하지 않는다. 같은 서버를 사용하면서 사용 구간이 조금이라도 겹치는 두 예약은 서로 충돌한다. 검사 결과에는 다른 예약과 한 번 이상 충돌하는 예약을 모두 포함해야 한다. 하나의 예약이 여러 예약과 충돌해도 결과 목록에는 그 예약 번호를 한 번만 넣는다. 또한 충돌한 예약을 임의로 취소하거나 검사 도중 목록에서 제거하지 않는다. 모든 충돌 여부는 처음 주어진 전체 예약 목록을 기준으로 판단한다. 한 예약의 구간이 다른 예약의 구간 안에 완전히 포함되는 경우도 충돌에 해당한다. 운영팀이 확인하기 쉽도록 결과 목록은 예약 번호의 오름차순으로 정렬한다. 같은 시작 시각이나 종료 시각을 가진 예약이 여럿이어도 예약 번호를 기준으로 출력 순서를 정한다. 예약 목록이 주어질 때 충돌하는 예약의 개수와 번호를 구한다. 충돌하는 예약이 하나도 없는 경우에도 정해진 두 줄의 출력 형식을 지켜야 한다.

입력

첫째 줄에 예약 수 N이 주어진다.
다음 N개 줄에 서버 번호 R, 시작 시각 S, 종료 시각 E가 공백으로 주어진다. 이 중 i번째 줄이 예약 i를 나타낸다.
모든 입력값은 정수이며, 1 ≤ N ≤ 12,000, 1 ≤ R ≤ 1,000, 0 ≤ S < E ≤ 1,000,000,000이다. 시각은 공통 기준 시점부터 지난 시간 단위 수이며, 입력은 시각순으로 정렬되어 있지 않을 수 있다.

출력

첫째 줄에 다른 예약과 한 번 이상 충돌하는 예약의 개수 C를 출력한다. C가 양수이면 둘째 줄에 해당 예약 번호 C개를 오름차순으로 공백으로 구분하여 출력한다. C가 0이면 둘째 줄에 0 하나를 출력한다.

6
1 10 20
1 20 30
2 12 25
1 15 18
1 29 35
2 25 26

4
1 2 4 5

4
3 0 5
3 5 8
4 0 8
3 8 9

0
0

4
7 3 12
7 4 5
7 6 7
7 3 12

4
1 2 3 4

출처: Devin.KR 자체 제작