[백준 11000번] 강의실 배정 (C++)

문제링크 : https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, S[200001], T[200001];
vector<pii>v;
priority_queue<int, vector<int>, greater<int>> pq; //작은 순으로

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

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

    sort(v.begin(), v.end()); //시작 시간 기준 정렬 (같으면 끝나는 시간 기준)

    for(int i=0; i<v.size(); i++)
    {
        pq.push(v[i].second); //강의실 추가
        if(pq.top() <= v[i].first) pq.pop(); //수업을 같이 듣는 경우 (강의실 제거)
    }

    cout << pq.size(); //총 강의실 갯수

    return 0;
}

 

우선 시작시간과 끝나는 시간을 벡터에 담아 시작 시간 기준으로 정렬해준다.

만약에 시작 시간이 같다면 끝나는 시간 기준으로 정렬하게 된다.

 

이제 우선순위 큐를 이용해 강의실을 추가해준다.

우선순위 큐의 우선순위는 값이 작은 순서이다.

넣어주는 값은 끝나는 시간을 넣어준다.

 

만약 끝나는 시간이 다음 강의 시작시간보다 같거나 작다면 수업을 같이 듣는 것이 가능하다.

따라서 강의실이 같으므로, 강의실을 제거 해준다.

이러면 강의실이 아에 없어지지만, 매번 끝나는 시간을 기준으로 강의실을 추가하기에 무사히 카운팅된다.

<예제>
1 3
2 4
3 5

정렬
1 3
2 4
3 5

우선순위큐
첫 푸쉬 3
3 > 2이므로 푸쉬 4 (작은 값 우선순위로 인해 top은 3)
3 <= 3이므로 top 제거
마지막 푸쉬 5

남은 값 4, 5 총 사이즈 2