[정올] 도서관

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

JUNGOL

그리디로 해결할 수 있습니다.

 

우선 문제부터 간단하게 요약하면, 

도서관에 학생들이 오는 시간과 가는시간이 주어집니다. 이 때, 한 명 이상의 학생이 머물렀던 가장 긴 시간과, 학생이 한 명도 머물지 않았던 가장 긴 시간을 공백으로 구분하여 출력해야 합니다. 

 

<Solution>

그리디를 사용하기 위해서 시작시간을 기준으로 정렬합니다. 

 

그리고 나서 순서대로 보면서 이전 학생과 비교해봅니다. 만약 이전 학생이 떠나는 시간보다 다음 학생의 도착 시간이 빠르다면, 구간이 이어집니다. 구간의 끝값을 다시 계산해 주어야 하는데, 시작시간이 느려도 이전 학생이 더 늦게 떠날 수도 있으므로

e_before = max(e,e_before);

이렇게 갱신시켜 주어야 합니다. 

 

하지만 다음 학생이 이전 학생이 떠난 후에 도착한다면, 학생이 한 명도 머물지 않았던 시간을 갱신해주는 작업을 해주어야 합니다. 그리고 이 경우에는 이전의 시작 시간 또한 바꾸어 주어야합니다. 

 

실제 구현을 보고 조금 더 이해하면 편할 것 입니다. 코드는 아래와 같습니다. 

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
// int S[10000+10];
// int E[10000+10];
int present;
int absent;
 
struct student{
    int S, E;
};
 
struct student students[10000+10];
 
void InputData(void){
    cin >> N;
    for (int i=0; i<N; i++){
        // cin >> S[i] >> E[i];
        cin >> students[i].S >> students[i].E;
    }
}
bool compare(struct student A, struct student B){
    return A.S < B.S;
}
 
void solution(){
    // sort by start time
    sort(&students[0], &students[N], compare);
 
    int s_before=0, e_before=0;
    int s,e;
    for(int i = 0; i<N; i++){
        s = students[i].S; e = students[i].E;
        if(s<=e_before){
            e_before = max(e,e_before);
            present = max(e_before-s_before, present);
        }
        else{
            absent = max(s-e_before, absent);
            s_before = s;
            e_before = e;
        }
 
         
    }
 
 
}
 
 
int main(void){
    InputData();// 입력받는 부분
 
    // 여기서부터 작성
    solution();
 
    cout << present << " " << absent << endl;// 출력하는 부분
    return 0;
}