백준 11000 강의실배정 c++ // 강의실배정 vs 회의실배정, pq cmp 구현시 주의점

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

1. 강의실배정 vs 회의실배정

1. 회의실배정 : 시작시간이 빠른것부터 배정하면 된다. 배정이가능하다면, ret++ 하면된다.

end변수를 사용한다 // 가장최근에 끝난 회의의 종료시간

int end = 0;
    int tot = 0;

    while(pq.size() > 0){
        sub = pq.top();
        if(end <= sub.start){ // 현재 꺼낸 회의가 현재 가장 최근에 종료된 회의 이후일때
            tot++;
            end = sub.end;
        }
        pq.pop();
        
    }

2. 강의실배정 :  시작시간기준으로정렬, pq는 종료시간기준으로 정렬

top.sec과 입력값.first를 비교하며 가능하다면(<=), top을 pop한다. 

즉, 같은 회의실 사용으로 처리하는것이다. -> pq.size가 써야되는 강의실의 수가 된다.

 

2. pq cmp 구현시 주의점

1. cmp는 매개변수가 같으면 거짓을 리턴해야함

2. bool operator 앞에 public 붙일것

 

3. 전체코드

#include <bits/stdc++.h>

using namespace std;


class cmp {
public:
    bool operator() (pair<int, int> p1, pair<int, int> p2) {
        if (p1.second == p2.second) return p1.first > p1.first;
        //!종료시간이 같다면! 시작시간이 작은것부터

        return p1.second > p2.second;
    }
};

int n,ret;
priority_queue<pair<int,int>, vector<pair<int,int>>,cmp> pq;
vector<pair<int, int>> v;


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

    for(int i=0;i<n;++i) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
    sort(v.begin(), v.end());
    //1. 시작시간 기준으로 정렬

    pq.push({ v[0].first,v[0].second });
    for (int i = 1; i < n;++i) {
        pq.push({ v[i].first,v[i].second });

        //top과 같은강의실을 사용가능하다면, top을 지운다.
        //같은강의실 사용으로 간주, 즉 pq.size가 강의실의 갯수가된다. 
        if (pq.top().second <= v[i].first) {
            pq.pop();
        }

    }
    cout << pq.size();
    return 0;

}