[C/C++] 백준 - 1374번 : 강의실

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

1374번: 강의실

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

출력

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

---

그리디 알고리즘의 대표문제 강의실 문제에 자료구조까지 적용해야하는 문제이다.

강의의 시작 시간과 끝시간 정보가 주어지고, 우리는 그 강의를 배정할 최소 강의실 개수를 알아야한다.

 

우리가 익히 알고있는 그리디 알고리즘의 회의실 배정 문제와 이 문제의 차이를 알아차린다면 빠르게 해결할 수 있다.

 

 

 

< 잘 알고 있는 그리디 알고리즘의 회의실 배정 >

• 시작 시간과 끝 시간이 주어진다.
• 하나의 회의실에 최대 몇 개의 회의가 진행가능한지 알아야 하는 문제이다.
• 모든 회의를 진행하는 것이 불가능한 경우가 존재한다.

 

< 위 문제 그리디 알고리즘 + 자료구조 회의실 배정 >

• 시작 시간과 끝 시간이 주어진다.
• 모든 회의를 진행해야한다는 가정이 존재한다.
• 모든 회의를 진행할 때 필요한 최소 강의실의 개수를 구해야하는 문제이다.

 

 

즉, 이 문제는 모든 회의를 진행시켜야하고 그 때 필요한 최소한의 강의실을 우리는 구해야한다.

따라서 정렬의 조건을 시작시간이 되어야한다. 가장 먼저 시작하는 회의부터 진행을 하고 다음에 진행해야하는 회의 시작시간과 우리가 전에 진행했었던 회의의 끝나는 시간과 비교하여 회의실이 추가로 필요한지 확인해주어야한다.

 

-> 정렬의 조건 : 회의의 시작시간

-> 회의실이 추가로 필요한지 확인 : 이미 진행한 회의의 끝나는 시간과 비교하여 추가로 회의실이 필요한지 확인 -> 우선순위 큐로 이미 진행한 회의의 끝나는 시간 정렬

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 987654321
#define endl '\n'

using namespace std;

typedef struct info{
    int number;
    int start;
    int end;
}info;

int N;
vector<info> op;

bool cmp(const info &lhs, const info &rhs){
    if(lhs.start == rhs.start) return lhs.end < rhs.end;
    return lhs.start < rhs.start;
}

void input(){
    cin >> N;
    op.resize(N);
    for(int i=0;i<N;i++){
        cin >> op[i].number >> op[i].start >> op[i].end;
    }
}

int solution(){
    sort(op.begin(), op.end(), cmp);
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(auto &t : op){
        if(pq.empty() || t.start < pq.top()) {
            pq.push(t.end);
        }
        else{
            pq.pop();
            pq.push(t.end);
        }
    }
    return pq.size();
}

int main(){
    fastio;
    input();
    cout << solution() << endl;

    return 0;
}