[11000] 강의실 배정

분류

• 그리디
• 우선순위 큐
• 정렬

 

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

11000번: 강의실 배정

 

 

문제

 

풀이

[주요 로직]

이미 배치된 수업들(m개)의 끝나는 시간 ≤ 지금 배치하려는 수업의 시작시간(1개)

true ) 이미 있는 교실중 하나에 배치 가능 

false ) 새로운 교실이 필요함 (교실수 ++)

이제 이걸 총 수업의 갯수(n개)만큼 반복해야한다.

 

[고려사항]

문제는 이를 얼마나 효율적으로 하느냐다.

생각해보자, 이미 배치된 수업 m개를 전부 검사해볼 필요는 없다.

"배치된 수업 m개의 끝나는 시간 중 최소" 와 "배치해야할 수업의 시간 중 최소" 를 비교한다면 1회안에 결론낼 수 있다. 

 

[해결법]

이미 배치된 수업들의 끝나는 시간 중 최소 ≤ 배치이전인 수업들의  시작시간 중 최소(1개)

false) 배치된 수업 m개중 최소 시간이 배치해야할 수업의 시간 중 최소보다 크다면, 남은 m-1개는 볼 필요도 없이 더 클 것이다.

즉, 새로운 교실이 필요하다 ( 교실수 ++ )

true) 새로운 교실이 필요하지 않고, 어딘가 교실에 배치한다. (해당 최소값은 이제 갱신될것 → 없어짐)

 

결국 양 쪽다 최소를 알아야 하는데, 

배치 이전인 수업들 → 배열에 넣고 1회만 시작시간 기준으로 sort하면 됨 

• 갱신될 필요 없음 
• 시작시간임

배치 이후인 수업들 → 우선순위 큐로 끝나는 시간만 넣어서 구현하면 됨

• 갱신여지가 있음
• 끝나는 시간임

 

 

코드 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

priority_queue<int, vector<int>, greater<>> pq;
vector<pair<int, int>> v;


int main() {

    int N, s, t;
    cin >> N;

    v.assign(N, {0, 0});

    for (int i = 0; i < N; i++) {
        cin >> s >> t;
        v[i] = {s, t};
    }

    sort(v.begin(), v.end());

    int ans = 1; //최초는 넣어두기
    pq.push(v[0].second);

    for (int i = 1; i < N; i++) {

        if (pq.top() > v[i].first) {
            ans++;//새로운 교실이 필요
        } else {
            pq.pop();//새로운 교실 필요 x 
        }
        pq.push(v[i].second);//배치완료이므로 배치 완료된 집단에 넣어줘야함

    }

    cout << ans;


}

 

삽질

삽질이랄 것도 없다. 그냥 생각못해봄 하하