[백준 11000 C++][G5] 강의실 배정

⭐️ 난이도

Gold 5

---

⭐️ 문제

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

11000번: 강의실 배정

 

---

⭐️ Idea flow

 

N개의 강의에 대해서 각각의 시작 시간과 끝나는 시간이 주어졌을 때, 강의실을 얼마나 적게 사용할 수 있는지 구해야 하는 문제이다.

문제 지문에서 "Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다"고 주어져있다.

이 말은, i번째 강의의 시작시간 Si가 k번째 강의의 끝나는 시간 Tk보다 크거나 같다면, 해당 강의실에서 강의를 이어서 진행할 수 있다는 뜻이다.

 

강의실을 가장 적게 쓰려면 중간에 공백을 최대한 줄여야 한다.

그러기 위해서는 어떤 강의가 끝난 이후에 시간 시간이 제일 빠른 강의를 배치해야 한다.

 

priority_queue(우선순위 큐)를 이용해서 풀 수 있었는데, pq를 항상 올림차순으로 설정해놓고 강의의 끝나는 시간 만을 저장한다.

이후에 강의의 시작 시간과 pq의 값을 비교하여 만일 시작 시간이 더 빠르다면 pq에 push하여 강의실의 개수를 늘린다.

 

[전체적인 알고리즘]

1. 먼저 모든 강의를 시작 시간 - 끝나는 시간이 빠른 순서로 정렬한다.

2. 우선 첫 번째 강의의 끝나는 시간을 pq에 push한다.

3. 이제 두 번째 강의부터 마지막 강의까지 반복문을 통해 확인한다.

3-1. 만일 i번째 강의의 시작 시간이 pq.top()-[기존 강의의 끝나는 시간]과 같거나 더 크다면, 기존의 강의실을 계속 쓸 수 있다는 의미이다.

      따라서 pq.pop() 이후 i번째 강의의 종료 시간을 pq에 push한다.

3-2. 만일 i번째 강의의 시작 시간이 pq.top()-[기존 강의의 끝나는 시간]보다 빠르다면, 기존의 강의실을 사용할 수 없고,

      새로운 강의실에서 강의를 해야 한다.

      따라서 i번째 강의의 종료 시간을 pq에 push한다.

4. 반복문을 모두 진행하고, pq의 size가 필요한 강의실의 개수이다.

 

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

#define INF 987654321
#define MAX 1000000 + 1
using namespace std;

// 11000 - 강의실 배정
int n;
vector<pair<int, int>> lecture;


void input(){
    cin >> n;
    lecture.assign(n, {0,0});
    for(int i = 0; i < n; i++){
        cin >> lecture[i].first >> lecture[i].second;
    }

    sort(lecture.begin(), lecture.end());
}

int solve(){
    priority_queue<int, vector<int>, greater<>> pq;
    pq.push(lecture[0].second);

    for(int i = 1; i < n; i++){
        int startTime = lecture[i].first;
        int endTime = lecture[i].second;

        if(startTime >= pq.top()){ // 시작하는 시간이 끝나는 시간 이후라면
            pq.pop();
            pq.push(endTime);
        }
        else{
            pq.push(endTime);
        }
    }
    return pq.size();
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();

    cout << solve();

    return 0;
}