회의실 정리 시간 계산

문제

사내 회의실 예약 시스템의 기록을 분석하려 한다. 예약은 N건이며 각 예약은 시작 일시와 종료 일시로 주어진다. 일시는 YYYY-MM-DD HH:MM 형식이고 24시간제이며, 윤년 규칙(4로 나누어떨어지면 윤년, 100으로 나누어떨어지면 평년, 400으로 나누어떨어지면 다시 윤년)을 따른다. 종료 일시는 시작 일시보다 항상 뒤이며 날짜가 바뀌어도 된다. 회의가 끝난 회의실은 다음 회의를 위해 G분 동안 정리해야 하므로, 종료 일시로부터 G분이 지난 시각에야 다른 예약에 쓸 수 있다. 정리가 끝나는 시각과 같은 시각에 시작하는 예약은 그 회의실을 쓸 수 있다. 모든 예약을 겹침 없이 소화하기 위해 필요한 회의실의 최소 개수를 구하라. 예약 하나는 시작 일시부터 종료 일시에 정리 시간 G분을 더한 시각까지 방 하나를 점유한다고 본다.

입력

첫 줄에 N과 G가 공백으로 구분되어 주어진다. 이어지는 N개의 줄에 각각 예약 하나가 시작 날짜, 시작 시각, 종료 날짜, 종료 시각 순서로 공백으로 구분되어 주어진다. 1 ≤ N ≤ 10000, 0 ≤ G ≤ 1440이다. 모든 일시는 2000-01-01 00:00 이상 2100-12-31 23:59 이하이다.

출력

필요한 회의실의 최소 개수를 정수 하나로 출력한다.

3 10
2024-02-28 23:00 2024-02-29 01:00
2024-02-29 01:10 2024-02-29 02:00
2024-02-29 01:05 2024-02-29 03:00

2

2 0
2023-12-31 23:30 2024-01-01 00:00
2024-01-01 00:00 2024-01-01 00:30

1

출처: Devin.KR 자체 제작