[PS] 백준 #11000 강의실 배정 문제 풀이

[ 문제 풀이 ]

• Problem : 백준 #11000
• 구분 : Greedy, pq(우선순위 큐), ds
• 난이도 : Gold 5
• 풀이 방법 :
  • 한 강의실 당 강의 시간이 겹치지 않는 수업을 최대한 몰아줘야 최소 강의실 개수를 구할 수 있습니다.
  • 강의실에 시작 시간이 빠른 것 수업부터 조사해서 같은 강의 실에 넣을 수 있는지 판단해 강의실을 할당하는 그리디 알고리즘(현재 조건에서 가장 최선의 경우를 할당)을 사용했습니다.
    
    
  • (시작 시간, 종료 시간)으로 구성된 수업을 pq에 넣고, 시작 시간이 빠른 것부터 정렬하도록 했습니다. (만약, 시작 시간이 같다면 종료 시간이 가장 빠른 순서대로 정렬하도록 구성했습니다.)
  • 수업 시작 시간은 이미 정렬이 된 상태이기 때문에 종료시간과 다음 수업 시작 시간을 비교하기 위해 종료 시간을 저장할 pq를 하나 더 선언해 주었습니다. 여기서 pq 내부의 한개의 요소는 강의실을 의미합니다.
  • 수업을 한개씩 pq에서 빼면서, 다음과 같은 로직을 따르게 했습니다.
    • 강의실 우선순위 큐(tq)가 비었다면, 현재 강의실이 0개이므로 강의실을 생성해 해당 수업을 할당합니다.
      👉🏻 종료시간을 tq에 저장합니다.
    • 강의실 우선순위 큐(tq)가 비어있지 않다면, 현재 강의실 중 종료 시간이 가장 이른 강의실(tq.top())의 종료시간과 현재 수업의 시작 시간을 비교합니다.
      • 만약 종료시간이 현재 수업의 시작 시간보다 작거나 같다면, 해당 수업은 강의실의 기존 수업과 겹치지 않으므로 할당할 수 있습니다.
        👉🏻 해당 강의실의 종료시간을 갱신해줍니다.
      • 만약 종료시간이 현재 수업의 시작 시간보다 크다면, 해당 강의실의 수업과 겹치므로 할당할 수 없습니다.
        👉🏻 새로운 강의실을 생성해 해당 수업을 할당합니다.
  • 강의실 배정이 끝나면 tq.size() = 강의실의 개수를 출력해줍니다.
  • 해당 알고리즘의 시간복잡도는 O(nlogn)입니다.

[ 🤟🏻 code from ss-won ]

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
using namespace std;
struct compare{
    bool operator()(pair<int,int> a, pair<int,int> b){
        if(a.first == b.first){
            return a.second > b.second;
        }
        return a.first > b.first;
    }
};
priority_queue<pair<int,int>, vector<pair<int,int>>, compare> pq;
priority_queue<int, vector<int>, greater<int>> tq;
int n, s, t;

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    
    /* == inputs == */
    // pq에 넣어 시작시간 순서로 정렬
    // 시작시간이 같으면 종료시간이 순서로 정렬
    while(n--){
        cin >> s >> t;
        pq.push({s,t});
    }
    
    /* == 강의실 배정 == */
    while(!pq.empty()){
    	// 정렬된 수업(s, t)을 꺼내 강의실 배정하기
        tie(s,t) = pq.top(); pq.pop();
        if(tq.empty()){
            tq.push(t);
        }
        else{
            // 현재 배정한 강의실의 종료시간 중 최소값과 비교했을 때,
            // 강의실 종료시간보다 시작 시간이 크거나 같으면 
            // 강의실 종료시간 갱신
            if(s >= tq.top()){
                tq.pop();
                tq.push(t);
            }
            // 그렇지 않으면, 새로운 강의실 배정
            else{
                tq.push(t);
            }
        }
    }
    // 강의실의 최소 개수 출력
    cout << tq.size();
    return 0;
}x