[Greedy] 백준 11000번 "강의실 배정" C++ 풀이

문제 링크

• https://www.acmicpc.net/problem/11000

풀이

• 해당 문제를 풀기 위해, 요소 삽입과 동시에 내부 요소를 정렬하는 Priority Queue 라는 자료구조를 사용했으며, 개념에 대해선 추가적인 숙지가 필요합니다.

  • https://wooono.tistory.com/392

• 이제, 문제에서 주어진 예제 (1,3) (2,4) (3,5) 를 통해서 풀이해보겠습니다.

• 우선 수업 목록을, 시작 시간 기준으로 오름차순 정렬합니다.

  

• 그 다음, 시작시간이 가장 빠른 수업(1, 3) 의 종료시간(3) 을 Priority Queue 에 push 합니다.

  

• 그리고, 두 번째로 시작시간이 빠른 수업(2,4) 의 종료시간(4) 을 Priority Queue 에 push 합니다.

  

  • 이제, Priority Queue 의 top 종료시간(3) 과 두 번째 수업의 시작 시간(2) 를 비교합니다.
  • top 종료시간(3) 이 두 번째 수업의 시작 시간(2) 보다 늦으므로, 두 강의는 같은 강의실에서 진행할 수 없습니다.

• 그리고, 세 번째로 시작시간이 빠른 수업(3,5) 의 종료시간(5) 을 Priority Queue 에 push 합니다.

  

  • 이제, Priority Queue 의 top 종료시간(3) 과 세 번째 수업의 시작 시간(3) 를 비교합니다.
  • top 종료시간(3) 이 세 번째 수업의 시작 시간(3) 과 같으므로, 두 강의는 같은 강의실에서 진행할 수 있습니다.
  • 따라서, Priority Queue 의 top 종료시간(3) 을 pop 합니다.

• 모든 수업에 대한 탐색이 끝나면, Priority Queue 의 Size (총 강의실 개수) 를 출력합니다.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

// 수업 시간 목록
vector< pair<int, int> > class_time;

// 종료 시간 큐 (가장 작은 값이 우선순위가 되는 큐)
priority_queue< int, vector<int>, greater<int> > pq_less;

int greedy(int class_count){
    // 첫 번째 수업의 종료 시간을 pq 에 삽입
    pq_less.push(class_time[0].second);

    // 필요한 강의실 탐색
    for(int i=1; i<class_count; ++i){
        // i 번째 수업의 종료 시간을 pq 에 삽입
        pq_less.push(class_time[i].second);
        // top 의 종료 시간보다 i 번째 수업이 늦게 시작한다면, 같은 강의실에서 진행 가능
        if (pq_less.top() <= class_time[i].first){
            // 기존의 top 은 제거
            pq_less.pop();
        }
    }
    // pq 의 요소개수가 곧 필요한 강의실 개수
    return pq_less.size();
}

int main(){

    // 수업 개수
    int n;
    cin >> n;

    // 수업 개수 만큼 수업 시간 저장
    for(int i=0; i<n; ++i){

        // 수업 시작, 종료 시간
        int start_time, end_time;
        cin >> start_time >> end_time;

        // 수업 시간 저장
        class_time.push_back(make_pair(start_time, end_time));
    }

    // 시작 시간 기준으로 수업 정렬
    sort(class_time.begin(), class_time.end());

    cout << greedy(n) << endl;

}

참고

• https://novlog.tistory.com/24