아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

종점

면접 대비

시간 제한1초메모리 제한1024 MB

요약
N대 버스의 도착 시각과 출발 시각이 주어질 때, 같은 시각에는 출발을 도착보다 먼저 처리한다는 규칙 아래 모든 버스가 기다리지 않도록 필요한 최소 정비 공간 수를 구한다.
난이도

보통10점 중 4점

유형
정렬, 구간, 그리디, 구현
정답자
아직 제출이 없습니다

문제

주행을 마친 버스들이 종점에 들어온다. 종점에 들어온 버스는 정비를 받을 자리로 들어간다. 즉, 종점에 버스 4대가 있다면 버스를 정비할 공간이 최소 4개 필요하다. 같은 시각에 종점으로 들어오는 버스 A와 종점에서 출발하는 버스 B가 있으면, 버스 B가 먼저 종점에서 출발하고 그다음에 버스 A가 종점으로 들어온다.

버스 시간표는 매일 같고, 종점에 들어오는 시각과 나가는 시각도 매일 같다.

이번에 버스 시간표가 바뀌어서, 버스를 정비할 공간이 최소 몇 개 필요한지 다시 계산해야 한다. 이 계산을 도와주자.

입력

첫째 줄에 종점에 들어오는 버스의 수 NN이 주어진다.

둘째 줄부터 N+1N+1번째 줄까지 각 버스가 종점에 들어오는 시각과 종점에서 나가는 시각이 주어진다. 한 버스의 나가는 시각은 들어오는 시각보다 늦다.

시각은 HH:MM:SS.sss 형식으로 주어진다. HH는 시, MM은 분, SS는 초, sss는 밀리초를 나타낸다.

출력

버스를 정비할 공간이 최소 몇 개 필요한지 출력한다.

제한

  • 1≤N≤100,0001 ≤ N ≤ 100,000
  • 0≤HH<240 ≤ HH < 24
  • 0≤MM<600 ≤ MM < 60
  • 0≤SS<600 ≤ SS < 60
  • 0≤sss<10000 ≤ sss < 1000

예제1

  1. 예제 1

    입력
    4
06:00:00.000 06:30:00.000
06:10:45.000 06:15:00.000
06:30:00.000 06:40:00.000
06:01:00.001 06:40:00.001
    예상 출력
    3