강의실
면접 대비시간 제한2초메모리 제한128 MB
N개 강의의 시작, 종료 시간이 주어질 때 겹치는 시간이 없도록 배정할 최소 강의실 수를 구하는 문제입니다.
문제
N개의 강의가 있다. 각 강의의 시작 시각과 종료 시각이 주어진다. 가능한 한 적은 수의 강의실만 사용해서 모든 강의를 배정하려고 한다.
한 강의실에서는 같은 시각에 두 개 이상의 강의를 진행할 수 없다. 다만 어떤 강의가 끝나는 시각과 다른 강의가 시작하는 시각이 같으면, 두 강의를 같은 강의실에 배정할 수 있다.
모든 강의를 진행하는 데 필요한 강의실 수의 최솟값을 구하라.
입력
첫째 줄에 강의의 개수 N (1 <= N <= 100,000)이 주어진다.
다음 N개의 줄에는 각 강의 정보가 강의 번호 시작 시각 종료 시각 형식으로 주어진다. 강의 번호는 1부터 N까지이며, 입력에서는 임의의 순서로 주어질 수 있지만 각 번호는 정확히 한 번씩만 등장한다.
시작 시각과 종료 시각은 0 이상 1,000,000,000 이하의 정수이고, 시작 시각은 종료 시각보다 작다.
출력
첫째 줄에 필요한 강의실 수의 최솟값을 출력한다.