[C++] 백준 온라인 저지 11000번 강의실 배정 풀이

모든 수업을 들을 수 있는 최소 강의실 갯수를 구하는 문제

 

---

문제

 

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

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

 

입력

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

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 10^9)

 

출력

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

 

 

풀이

 

 항상 나를 힘들게 하는 시간초과... 처음에 짰던 로직의 흐름은 맞았지만 계속 시간초과 나서 수정해야 했습니다. 

 

처음에 짰던 코드

 입력으로 주어지는 강의 시간들을 우선순위 큐에 저장한다. 우선순위 큐는 최소힙으로 구성해서 강의 시작시간이 빠른 순서대로 앞에 온다. 

 강의 종료시간을 저장할 벡터를 하나 만든 뒤 벡터에 저장되어 있는 종료시간들 중 맨 앞에 있는 강의의 시작시간보다 작거나 같은 값이 있으면 해당 인덱스의 종료 시간을 현재 강의의 종료시간으로 갱신한다. 없다면 벡터에 현재 종료시간을 추가한다. 이 과정을 큐가 빌 때까지 반복한다. 

 반복이 끝나고 나면 강의 종료시간이 저장된 벡터의 길이를 출력한다. 

 

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

using namespace std;

struct compare
{
    bool operator()(const pair<int, int>& a, const pair<int, int>& b)
    {
        if (a.first > b.first) return true;
        if (a.first == b.first && a.second > b.second) return true;
        
        return false;
    }
};

int main()
{
    int N;
    cin >> N;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> classes;
    for (int i = 0; N > i; i++)
    {
        int a, b;
        cin >> a >> b;
        classes.emplace(make_pair(a, b));
    }
    
    vector<int> endTime;
    while (!classes.empty())
    {
        auto cur = classes.top();
        classes.pop();
        
        int a = cur.first;
        auto it = find_if(endTime.begin(), endTime.end(), [&a](const int& i) {return i <= a;});
        
        if (endTime.end() == it)
        {
            //모든 강의실을 탐색했는데 가능한 강의실이 없다면 새 강의실 추가
            endTime.emplace_back(cur.second);
        }
        else
        {
            //다음 수업 시작시간이 index번째 강의실 수업 종료시간보다 크거나 같다면 종료 시간 갱신
            auto index = it - endTime.begin();
            endTime[index] = cur.second;
        }
    }
    
    cout << endTime.size();
    
    return 0;
}

 

 근데 90%에서 시간초과가 나더라고용...ㅠ 하긴 저게 정렬된 벡터도 아니고... 그래서 질문 게시판을 보며 아이디어를 얻어서 다음과 같이 수정했습니다. 

 

 

수정한 코드

 입력으로 주어지는 강의 시간들을 벡터에 저장한 뒤 강의 시간이 빠른 순서대로 앞에 오도록 정렬한다(sort 함수 사용). 

 강의 종료시간을 저장할 우선순위 큐(최소 힙)를 만든다. 종료시간을 최소힙으로 만드는 이유는 

 

 

 이런 입력이 주어졌을 때 첫번째 강의가 끝나는 시간인 7이 되기 전 까지는 시작 시간이 2, 3, 4인 강의는 첫번째 강의가 진행중인 강의실을 쓸 수 없기 때문에 다른 강의실을 써야 한다. 그런데 2, 3, 4 강의들은 시간이 연속적으로 배치되어 있기 때문에 같은 강의실을 계속해서 사용할 수 있다.

 어차피 현재 확인하고 있는 강의의 시작시간보다 늦게 끝나는 강의실은 쓸 수 없기 때문에 굳이 확인하는 것은 의미가 없다. 현재 사용중인 강의실들 중 가장 빨리 끝나는 곳이 몇 시인지만 확인하면 그 강의실을 연결해서 쓸 수 있을지 아닐지 알 수 있다. 그 강의실을 쓸 수 있다면 그 강의실의 종료시간을 다음에 진행할 강의의 종료시간으로 갱신하면 되고 쓸 수 없다면 새로운 강의실을 하나 추가하면 된다. 이 아이디어를 진행하기에 적합한 컨테이너는 최소 힙이다. 

 

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

using namespace std;

int main()
{
    int N;
    cin >> N;
    
    vector<pair<int, int>> classes;
    for (int i = 0; N > i; i++)
    {
        int a, b;
        cin >> a >> b;
        classes.emplace_back(make_pair(a, b));
    }
    
    //강의 시간이 빠른 순서대로 정렬한다.
    sort(classes.begin(), classes.end(), [](const pair<int, int>& a, const pair<int, int>& b)->bool {
        if (a.first < b.first) return true;
        if (a.first == b.first && a.second < b.second) return true;
        
        return false;
    });
    
    priority_queue<int, vector<int>, greater<int>> endTime;
    endTime.emplace(classes[0].second);
    for (int i = 1; classes.size() > i; i++)
    {
        if (endTime.top() > classes[i].first)
        {
            //가장 빨리 끝나는 강의가 탐색중인 강의 시작시간보다 늦게 끝난다면 강의실 추가
            endTime.emplace(classes[i].second);
        }
        else
        {
            //일찍 끝난다면 가장 빠른 종료시간 갱신(top을 버리고 현재 종료시간을 추가한다)
            endTime.pop();
            endTime.emplace(classes[i].second);
        }
    }
    
    //모든 탐색이 끝나면 큐에는 최소 강의실 수 만큼 원소가 들어있다.
    cout << endTime.size();
    
    return 0;
}