[백준/C++] #11000 강의실 배정 (Greedy)

문제

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

 

 

구상

가장 처음에 왼쪽 그림처럼 2차원 배열을 만들어서 1번 강의실부터 시간들 채워나가며 몇번 강의실까지 사용하는지 알고자 했는데, S와 T의 범위가 10^9로 굉장히 커서 시간 복잡도에서 문제가 생겼다. 

 

그래서 오른쪽 그림과 같은 구상을 했는데, 먼저, 주어진 S와 T를 배열에 넣고, S(시작 시간)기준으로 정렬한다. 그리고, 끝시간은 최소힙에 하나씩 넣고 시작시간과 비교해 시작시간이 최소힙에 있는 끝시간보다 같거나 크면 힙의 top값을 pop하고, 현재 강의 시간의 끝 시간을 최소힙에 넣는다. 남아있는 강의들 중에서 시작 시간이 가장 빠른 강의가 이미 배정된 강의 중에서 가장 끝시간이 빠른 강의 뒤에 올 수 있는지 판단하는 것이다. 만일 끝나는 시간이 더 크다면, 이어서 못하기에 힙에 새로운 값이 추가되며 새로운 강의실을 써야 한다는 결과로 이어지는 것이다. 

 

알고리즘

현재의 상황에서 가장 최적의 값을 찾아가며 계속 계산을 이어가는 풀이이기에 Greedy 알고리즘을 쓴다고 할 수 있다. 

 

풀이 + 코드

참고로 최소힙을 구현할때, priority queue(우선순위큐)를 사용한다. 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define MAX 200001
#define endl "\n"
using namespace std;
/*
11000 강의실 배정
s에 시작해서 t에 끝나는 n개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 함
수업이 끝난 직후에 다음 수업을 시작할 수 있음
필요한 강의실의 개수를 출력
*/

int N; // ~200,000
vector<pair<int, int>> lectures(MAX);

void solution() {

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

    // 최소 힙을 사용하여 강의실 끝나는 시간 추적
    priority_queue<int, vector<int>, greater<int>> min_heap; // 오름차순 -> 최소힙
    min_heap.push(lectures[0].second);
    
    // 현재 강의의 시작 시간이 가장 빨리 끝나는 강의의 시간보다 크거나 같으면, 현재 강의는 해당 강의실에서 바로 시작할 수 있음
    for (int i = 1; i < N; ++i) {
        if (lectures[i].first >= min_heap.top()) {
            min_heap.pop(); // 최소 힙에서 그 끝나는 시간 제거 
        }
        min_heap.push(lectures[i].second); // 현재 강의의 끝나는 시간을 최소 힙에 추가
    }
    // -> 최소 힙에는 현재 사용 중인 강의실들의 끝나는 시간이 저장
    
    // 최소 힙의 크기가 필요한 강의실의 개수
    cout << min_heap.size() << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> N; 
    lectures.resize(N);

    for (int i = 0; i < N; ++i) {
        int S, T;
        cin >> S >> T;
        lectures[i] = { S, T };
    }

    // 로직
    solution();

    return 0;

}