백준 11000번 강의실 배정

김두현·2022년 12월 6일

목록 보기

36/133

🔒[문제 url]

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

🔑알고리즘

앞 강의가 끝난 시점 이후에 시작하는 강의는 한 강의실에서 수강이 가능하다.
따라서, priority_queue(1)에 강의 시작시간을 기준으로 정렬하여 필요한 강의실을 세어보자.

문제를 다르게 해석하면, 겹치지 않고 이어지는 강의 리스트가 몇 개인가라고 해석할 수 있다.
겹치지 않기 위해서는, 앞 강의가 끝난 이후에 시작해야하므로 priority_queue(2)를 하나 더 생성하여 끝나는 시간을 오름차순으로 push하도록 하자.

끝나는 시간은 왜 priority_queue(2)에 담는가?

오름차순이 아닌 경우, 일찍 끝나 이을 수 있는 강의가 있음에도 잇지 못 할 수 있다.

어떻게 강의실 갯수를 갱신할까?

최초 상태의 queue(2)는 처음으로 시작하는 강의가 끝나는 시간이 담겨있다.
여기서 queue(1)의 top에 담긴 강의가 시작하는 시간은 둘 중 하나로 나뉜다.

queue(2)의 top에 담긴 값. 즉, 이전 강의가 끝나는 시간보다 빠른 경우
$\rarr$ 이어지지 못하므로 강의실을 추가한다.

queue(2)의 top에 담긴 값. 즉, 이전 강의가 끝나는 시간 이후인 경우
$\rarr$ 이어질 수 있는 강의가 있으므로 강의실은 추가하지 않는다.

🐾부분 코드

int n;
struct comp
{
/* 
 *  Why ascending by first value?
 *  Gap between pevious lecture's T and current lecture's S should be SHORT.
 *  But if ascending by second value, it may not happen.
 */
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        if (a.first == b.first) return a.second > b.second;
        else return a.first > b.first;
    }
};
// lecture info
priority_queue<pair<int, int>, vector<pair<int,int>>, comp> lec;
// T_i set, S_(i+1) have to larger than Tq's front
priority_queue<int, vector<int>, greater<int>> Tq

<변수 선언 및 정렬 기준>
강의 정보를 담을 priority_queue와 끝나는 시간을 담을 priority_queue를 선언한다. 강의 정보는 시작 시간을 기준으로 오름차순 정렬한다.
이때 시작 시간을 기준으로 정렬하는 이유는, 최대한 많은 강의를 잇기 위해서는 강의가 끝난 시간와 다음 강의가 시작하는 시간의 간격이 짧아야하기 때문이다.

void SOLVE()
{
    int ans = 1;

    Tq.push(lec.top().second);
    lec.pop();
    while (!lec.empty())
    {
        if (Tq.top() <= lec.top().first)
        {
            Tq.pop();
            Tq.push(lec.top().second);
            lec.pop();
        }
        else
        {
            ans++;
            Tq.push(lec.top().second);
            lec.pop();
        }
    }
    cout << ans;
}

<queue 처리 방식 구현>
위에서 설명한 알고리즘을 강의 정보가 담긴 queue가 빌때까지 반복한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
// 자료 구조
#include <queue>
using namespace std;

int n;
struct comp
{
/* 
 *  Why ascending by first value?
 *  Gap between pevious lecture's T and current lecture's S should be SHORT.
 *  But if ascending by second value, it may not happen.
 */
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        if (a.first == b.first) return a.second > b.second;
        else return a.first > b.first;
    }
};
// lecture info
priority_queue<pair<int, int>, vector<pair<int,int>>, comp> lec;
// T_i set, S_(i+1) have to larger than Tq's front
priority_queue<int, vector<int>, greater<int>> Tq; 

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int s, t; cin >> s >> t;
        lec.push({ s,t });
    }
}


void SOLVE()
{
    int ans = 1;

    Tq.push(lec.top().second);
    lec.pop();
    while (!lec.empty())
    {
        if (Tq.top() <= lec.top().first)
        {
            Tq.pop();
            Tq.push(lec.top().second);
            lec.pop();
        }
        else
        {
            ans++;
            Tq.push(lec.top().second);
            lec.pop();
        }
    }
    cout << ans;
}



int main()
{
    INPUT();

    SOLVE();
}