[백준] 1374 : 강의실

www.acmicpc.net/problem/1374

1374번: 강의실

---

• 입력 받은 강의들에 대해서는 시작 시간이 빠른 순으로 하는 우선순위 큐를 만든다.
• 강의실에 대해서는, 종료 시간이 가장 빠른 순으로 나오는 우선순위 큐를 만든다.
• 모든 강의들에 대해서 시작 시간 순으로 검사하는데, 현재 강의실 중 종료시간이 가장 빠른 강의실과 비교해나가며 추가한다.
• 더 좋은 풀이방법으로는, 시작시간과 종료시간을 한 쌍으로 보지 않고 각각 따로 정렬해준 뒤 비교해나가는 방법이 있겠다.

---

#include <iostream>
#include <queue>

using namespace std;

int N, temp, start, endd;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> lectures;
priority_queue<int, vector<int>, greater<int>> rooms;

int main(void)
{
    cin >> N;
    for(int i = 0 ; i < N ; i++)
    {
        cin >> temp >> start >> endd;
        lectures.push({start, endd});
    }

    // 첫 강의를 강의실에 하나 추가해놓고 시작
    rooms.push(lectures.top().second);
    lectures.pop();

    // 모든 강의를 배정하는데, 강의는 시작시간이 빠른 순으로 확인
    while(lectures.size())
    {
        // 기존 강의실 중에서 가장 빨리 끝나는 강의실에 새로운 강의 배정
        if(rooms.top() <= lectures.top().first)
        {
            rooms.push(lectures.top().second);
            rooms.pop();
        }
        // 가장 빨리 끝나는 강의실도 이번 강의와 시간이 맞지 않으면, 새로운 강의실 추가
        else
        {
            rooms.push(lectures.top().second);
        }
        lectures.pop();
    }

    cout << rooms.size() << endl;
}