[정올] [그리디] 2247 도서관 문제

정올, 그리디 알고리즘의 도서관 문제

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1508&sca=3020

정올 도서관은 학생들을 위하여 항상 열려있다. 학생의 입장에서는 아무 때든 도서관을 찾아 공부할 수 있어 편리하지만 정올 도서관의 입장에서는 그리 효율적이지 못했다.  학생이 몇 명 되지 않는 시간에도 모든 시설을 열어야 하며 심지어 학생이 오지 않는 시간에도 도서관을 열고 있어야 했다.

 

이러한 문제점을 개선하고자 도서관 관리자인 창환이는  학생들의 도서관 이용 시간을 분석하고자 한다. 먼저 하루 중 도서관에 학생들이 머물고 있는 가장 긴 시간과 학생들이 다녀간 전체 시간 중 학생이 하나도 없었던 가장 긴 시간을  알아보는 것이다.

 

예를 들어, 오늘 도서관에 온 학생이 준호, 서훈, 서은, 규찬 4명이고 준호의 이용시간은 1에서 3, 서훈의 이용시간은 3에서 6, 서은의 이용시간은 3에서 8, 규찬의 이용시간은 12에서 17 일때, 학생들이 머물었던 가장 긴 시간은 7, 학생들이 하나도 없었던 가장 긴 시간은 8~12까지 4가 된다.

 

N(1≤N≤10,000)의 학생이 도서관을 이용한다고 할 때, 다음을 계산하는 프로그램을 작성하시오. 
 - 적어도 한 명 이상의 학생이 머물었던 가장 긴 시간 
 - 학생들이 다녀간 전체 시간 중 학생이 한 명도 머물지 않았던 가장 긴 시간

 

첫 줄에 정수 N(1≤N≤10000)이 입력된다.

두 번째 줄부터 N개의 줄에 걸쳐 두 정수 S, E(1≤S≤E≤231-1) 가 입력된다. S는 도서관에 들어온 시각 E는 학생이 도서관을 나간 시각이다.

한 명 이상의 학생이 머물었던 가장 긴 시간과 학생이 한 명도 머물지 않았던 가장 긴 시간을 공백을 구분하여 한 줄에 출력하시오.

[Copy] 4 1 3 3 6 3 8 12 17

[Copy] 7 4

* 들어온 시간 순서대로 정렬한 다음, 시간을 비교해 가면서 사람이 있는 시간은 길이를 재고

  사람이 없는 시간이 나오면 없는 시간을 확인하여, 있고, 없고가 반복될 때마다 확인하여 처리한다.