[Algorithm] Baekjoon 11000번 : 강의실 배정

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

 
 
using namespace std;
 
struct Node
{
    int start;
    int end;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.start < b.start;
}
 
int n, a, b;
vector<Node> nodes;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
        nodes.push_back({ a,b });
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
    priority_queue<int, vector<int>, greater<int>> pq;
 
    pq.push(nodes[0].end);
 
    for (int i = 1; i < nodes.size(); ++i)
    {
        if (nodes[i].start >= pq.top())
        {
            pq.pop();
            pq.push(nodes[i].end);
        }
        else pq.push(nodes[i].end);
    }
    
    cout << pq.size();
    
    return 0;
}
   
 
 

 

관련유형 문제를 풀어본 적 없다면 꽤 고민좀 해볼 것 같은 문제.

먼저 시작시간을 기준으로 오름차순 해줌으로써, 나중에 순회할 때 현재인덱스의 시작시간은 반드시 이전 시작시간보다 높다는것을 보장해준다.

 

그다음 우선순위큐에 제일 시간이 빠른것의 종료시간을 먼저 넣어주고, 이후의 인덱스부터 아래와 같은 로직을 수행한다.

우선순위는 항상 제일 작은 값을 뽑게 셋팅한다. 즉, 종료시간이 가장 작은걸 먼저 꺼낸다.

 

1. 우선순위큐의 top값을 검사한다.

    해당값이 현재 시작시간보다 작다면, 겹치지 않기때문에 강의실을 더 늘릴 필요가 없다.

    그렇기 때문에 우선순위큐에서 뽑아버리고, 현재 종료시간을 우선순위 큐에 넣어준다.

    현재 종료시간을 우선순위큐에 넣어줌으로써 현재 하나의 강의실로 연결된 시간대의 마지막시간이 몇시인지 알 수 있다. 

 

2. 만약 우선순위의 top값이 해당값이 현재시작시간보다 크다면, 즉 겹친다면 강의실을 더 늘려야한다.

    그렇기 때문에 해당값을 우선순위큐에서 뽑지 않고 현재 종료시간을 우선순위큐에 넣고 다음 인덱스로 넘어간다.

 

모든 탐색을 마치고 우선순위큐에 남은 개수를 출력해주면 정답이다.

 

시작시간이 오름차순이라는 기준이 정해져있기 때문에, 종료시간이 가장 작은걸 뽑아서 이을 수 있는지 검사만 해줘도 되는것이다. 

이거는 직접 테스트케이스보고 그려봐서 이해하는게 더 빠를 것 같으니 그려보는걸 추천한다.