강의실 최소 개수
실버 III의견: 0
\(N\)개의 강의가 있고, \(i\)번째 강의는 시각 \(s_i\)에 시작하여 시각 \(e_i\)에 끝난다(\(s_i < e_i\)). 한 강의실에서는 시간이 겹치는 두 강의를 동시에 진행할 수 없다. 단, 한 강의가 끝나는 시각과 다른 강의가 시작하는 시각이 같은 경우는 겹치지 않는 것으로 본다.
모든 강의를 진행하기 위해 필요한 강의실의 최소 개수를 출력하여라.
\(1 \le N \le 100\,000\), \(0 \le s_i < e_i \le 10^9\)
첫째 줄에 강의 수 \(N\)이 주어진다. 다음 \(N\)개의 줄에 각각 강의의 시작 시각 \(s_i\)와 종료 시각 \(e_i\)가 공백으로 구분되어 주어진다.
필요한 강의실의 최소 개수를 출력한다.
3
1 4
2 5
5 7
2강의 \(1\)과 \(2\)는 시간이 겹쳐 서로 다른 강의실이 필요하다. 강의 \(3\)은 강의 \(1\)이 끝난 뒤이므로 강의 \(1\)의 강의실을 다시 쓸 수 있어 총 \(2\)개면 된다.
2
1 2
2 3
1한 강의가 끝나는 시각에 다른 강의가 시작하므로 강의실 하나로 충분하다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
강의실 최소 개수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
강의실 최소 개수