백준 11000 강의실 배정 c++

문제 출처 :www.acmicpc.net/problem/11000

11000번: 강의실 배정

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

 

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위 큐

 

풀이

코드1은

중복이 허용되는 multiset에 오름차순으로 수업 종료시간을 저장하고,

multiset에 있는 수업 종료시간들이 새로 입력된 수업의 시작시간보다 크면

multiset에 값을 추가하는 풀이다.

multiset의 index를 도는 게 오래 걸려서 그런가... 시간 초과 코드다.

왜 시간 초과인 지 아시는 분은 댓글 좀 달아주세요!

 

코드2는

pair<int,int>에 수업 시작, 종료시간을 저장하고 오름차순으로 정렬한다.

우선순위 큐를 오름차순으로 선언하고, pair의 시작 부분(제일 먼저 시작되는 수업)의

종료시간을 큐에 저장하고, 이후 pair의 1부터 n인덱스까지 pair의 first(시작시간)보다

큐에 저장된 수업 종료시간이 크면 push, 반대면 pop and push한다.

코드1(시간초과)

#include<iostream>
#include<queue>
#include<set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    multiset<int,greater<int>> s;
    while (n--) {
        int st, fi;
        cin >> st >> fi;
        if (s.empty()) {
            s.insert(fi);
        }
        else { 
            multiset<int>::iterator i = s.begin();
            for (; i != s.end();) {
                if (*i <= st) {
                    s.erase(i++);
                    break;
                }
                else
                    i++;
            }
                    s.insert(fi);



        }
    }

    cout << s.size();



    return 0;
}

코드2(통과)

#include <iostream>
#include<queue>
#include<algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq;
    pair<int, int> *pa = new pair<int, int>[n];

    for (int i = 0; i < n;i++) {
        cin >> pa[i].first >> pa[i].second;
    }

    sort(pa,pa+ n);//오름차순 정렬
    pq.push(pa[0].second);//pq에 수업종료시간 저장

    for (int i = 1; i < n; i++) {
        if (pq.top() <= pa[i].first) {
            pq.pop();
            pq.push(pa[i].second);
        }
        else {
            pq.push(pa[i].second);
        }
    }

    cout << pq.size();

    return 0;
}