[백준] 11000 강의실 배정 priority-queue, greedy

문제 :

www.acmicpc.net/problem/11000

11000번: 강의실 배정

 

분석 :

이 문제는 언뜻 보면 19598번 최소 회의실 개수 문제와 비슷해 보인다.

하지만 N의 범위가 200,000d으로 O(N^2)으로 풀면 시간 초과가 발생한다 😢

그래서 자동으로 강의 끝나는 시간이 짧은 친구 순으로 검색할 수 있게끔 우선순위 큐를 이용하였다. (처음 써본다 .. 하하)

 

우선 순위큐는 

자료형 T, Container, 사용자 정의 비교 연산(struct, class - operator 연산자) 이 3가지를 정의해 줘야 하고 

pq.pop시 사용자가 정의한 우선순위 순으로 먼저 나가게 된다. 

 

구상한 알고리즘 

1. 우선 v 벡터에 pair 자료형으로 start, end 를 넣어 배열 생성

2. v 벡터 시작 시간 빠른 순으로 sort

3. 우선순위 큐 pq에 v 벡터 첫번째 원소 삽입 

4. v벡터 1번째 인덱스부터 비교

4-1) 우선순위 큐 pq에 있는 끝나는 시간이 가장 빠른 회의가 v 벡터 시작 시간보다 크다면 

다른 강의실을 할당해줘야 한다. 따라서 cnt 증가, 우선 순위 큐에 push

4-2) 우선순위 큐 pq의 끝나는 시간이 다음 회의 시작 시간보다 작다면 회의 이어서 할 수 있으므로 

cnt 증가하지 않고, 우선 순위 큐에 push 

 

 

c++ 코드 :

//
//  11000_lecture_room.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/03/07.
//

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
vector<pair<int, int>> v;

bool startTime(const pair<int, int> &a, const pair<int, int> &b){
    if(a.first == b.first){
        return a.second < b.second;
    }
    return a.first < b.first;
}

struct compare {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b){
        if(a.second == b.second){
            //끝나는 시간이 같으면 시작 시간이 빠른 순
            return a.first > b.first;
        }
        //끝나는 시간이 빠른 순
        return a.second > b.second;
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;




int find_room_count(int n){
    int cnt = 1;
    sort(v.begin(), v.end(), startTime);
    //정렬된 첫번째 원소 삽입(시작 시간 빠른 순)
    pq.push(v.at(0));
    
    for(int i = 1; i < n; i++){
        if(pq.top().second > v.at(i).first){
            pq.push(v.at(i));
            cnt++;
        }else{
            pq.pop();
            pq.push(v.at(i));
        }
    }
    return cnt;
    
}

int main(){
    int n;
    scanf("%d", &n);
    
    for(int i =0; i < n; i++){
        int start, end;
        scanf("%d %d", &start, &end);
        v.push_back(make_pair(start, end));
    }
    
    int count = find_room_count(n);
    printf("%d", count);
    
    return 0;
}