항공권 보호 서비스의 최대 동시 이용

문제

한 항공권 관리 서비스는 발권된 항공권마다 비행 중 보호 기능을 제공한다. 백엔드 담당자는 처리 용량을 점검하기 위해 보호 기능이 동시에 활성화되는 항공권 수를 조사한다. 항공권 한 장에는 출발지의 현지 출발 시각과 도착지의 현지 도착 시각이 저장되어 있다. 두 지역의 시차가 다를 수 있으므로 현지 시각의 문자열만 비교해서 비행 순서를 판단할 수 없다. 각 시각에는 UTC에 대한 시차가 분 단위의 정수로 함께 주어진다. 현지 시각은 UTC 시각에 이 시차를 더한 값이다. 예를 들어 시차가 540이면 현지 시각에서 540분을 빼서 UTC 시각을 얻는다. 시차는 해당 시각에 이미 확정된 값이므로 다른 시간대 규칙이나 계절별 변경을 적용하지 않는다. 날짜를 넘나드는 계산은 그레고리력을 따른다. UTC로 바꾼 출발 시각을 S, 도착 시각을 E라고 한다. 보호 기능은 S부터 활성화되고 E에는 종료된다. 따라서 활성 구간은 시작을 포함하고 끝을 포함하지 않는 [S, E)다. 같은 시각에 어떤 항공권의 보호 기능이 끝나고 다른 항공권의 보호 기능이 시작되면, 끝난 항공권은 그 시각의 활성 개수에 포함하지 않는다. 동일한 정보의 항공권도 각각 별도로 센다. 모든 입력 시각은 분 단위이며 초는 항상 0이다. 시각 t에서 시작하는 1분 구간은 [t, t+1분)을 뜻한다. 보호 기능의 상태는 이러한 구간 안에서 바뀌지 않는다. 조사 대상은 가장 이른 UTC 출발 시각부터 가장 늦은 UTC 도착 시각 직전까지다. 이 범위에서 동시에 활성화되는 항공권 수의 최댓값 K를 구한다. 또한 활성 개수가 K인 1분 구간들의 총개수 T와, 그러한 구간 중 가장 이른 시작 시각 F를 구한다. 최대 상태가 여러 번 나누어 나타나면 모든 구간의 길이를 더해야 하며, 사이에 최대 상태가 아닌 시간이 있더라도 하나의 연속 구간으로 합치지 않는다. F는 UTC 날짜와 시각으로 출력한다. 항공권은 적어도 한 장이고 모든 비행 시간이 양수이므로 K, T, F는 항상 존재한다.

입력

첫째 줄에 항공권 수 N이 주어진다. N은 1 ≤ N ≤ 5,000인 정수다.
다음 N개 줄에는 출발 날짜, 출발 시각, 출발 시차, 도착 날짜, 도착 시각, 도착 시차가 공백으로 구분되어 주어진다.
날짜는 YYYY-MM-DD 형식의 2026년 중 유효한 날짜다. 시각은 HH:MM 형식이며 00 ≤ HH ≤ 23, 00 ≤ MM ≤ 59다. 월, 일, 시, 분은 각각 두 자리다.
각 시차는 -720 이상 840 이하인 15의 배수인 정수다. UTC로 환산한 도착 시각은 출발 시각보다 반드시 늦으며, 비행 시간은 1분 이상 2,880분 이하다. 현지 날짜가 2026년이어도 UTC 날짜는 인접한 다른 해가 될 수 있다.

출력

첫째 줄에 최대 동시 활성 항공권 수 K를 출력한다. 둘째 줄에 가장 이른 시작 시각 F를 UTC 기준 YYYY-MM-DD HH:MM 형식으로 출력한다. 월, 일, 시, 분은 각각 두 자리로 출력한다. 셋째 줄에 최대 상태인 시간의 총길이 T를 분 단위 정수로 출력한다.

3
2026-04-02 09:00 540 2026-04-02 11:00 540
2026-04-02 01:00 0 2026-04-02 03:00 0
2026-04-02 11:00 540 2026-04-02 12:00 540

2
2026-04-02 01:00
120

3
2026-08-10 10:00 0 2026-08-10 11:00 0
2026-08-10 10:30 0 2026-08-10 12:30 0
2026-08-10 12:00 0 2026-08-10 13:00 0

2
2026-08-10 10:30
60

1
2026-01-01 00:10 60 2026-01-01 00:40 60

1
2025-12-31 23:10
30

출처: Devin.KR 자체 제작