문제 설명

• 입력
  • 첫번째 줄에는 N(Input의 개수)이 입력됨
  • 두번째 줄에는 강의가 시작되는 S와 강의가 끝나는 T의 입력이 주어짐
• 입력 예시

• 출력 예시

• 설명

  • S에 시작해서 T에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 진행 해야함
  • 수업이 끝난 직후에 다음 수업을 시작할 수 있다 (연강이 가능)

• 문제 아이디어

  • 처음에는 강의를 2차원 배열로 입력받고 강의가 끝나는 시간을 기준으로 정렬을 해서 배열을 탐색하는 데 끝항을 temp에 담고 만약 끝 항의 시간과 첫 항의 시간이 겹쳤을 경우 cnt를 증가시키는 방법으로 구현을 했었다.
  • 이 경우 생기는 문제는 (1,3),(2,4),(3,5) 를 입력받았다고 가정해보자
    • 1,3 후 2,4가 시작되어야하니 2개가 만들어진다 이때 temp에는 4가 저장되어 있다
    • 하지만 3,5가 입력되었으니 실제로는 1,3이 끝나고 바로 3,5가 시작되어야 하는데
    • temp가 4라서 새로운 강의실이 만들어 진다.
    • 즉 중간에 다른 입력이 있는데 끝나는 시간과 시작하는 시간이 겹쳤을 때 문제가 생긴다.
  • 끝나는 시간을 기억하는 배열을 만들어 풀어 보려 했지만 계속 시간초과가 나서 해결하지 못함.

  → 새로운 아이디어를 생각해보자

  • 튜플로 시작과 시작 상태, 종료와 종료 상태로 나눈 후 쭉 정렬해서 시간 순서로 비교해버리면 되지 않을까?
  • 만약 시작을 할 경우 +1로 강의실을 증가시키고 강의가 종료되면 -1을 시키면 됨
  • for 문을 순회하며 계속 max 함수로 최댓값을 max_count에 저장시킴

  

import sys

n = int(input())
lectures = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

lectures_state = []

for start, end in lectures:
    lectures_state.append((start, 1))
    lectures_state.append((end, -1))

lectures_state.sort()

count = 0
max_count = 0

for _, state in lectures_state:
    count += state
    max_count = max(max_count, count)

print(max_count)