백준 1374번 강의실 : 골드 5

백준 1374번

예전에 이런 비슷한 문제를 풀었던 적이 있다

어떤 강의들의 ID, 시작, 끝 시간을 입력받고 모든 강의를 진행하기 위해 최소로 빌려야하는 강의실의 개수를 구하는 문제이다

사실 강의 번호는 쥐뿔도 필요 없는 문제인데 왜 있는지 모르겠네

강의 시작과 종료는 0 이상 10억 이하이니 int로도 충분하다

풀이

나는 이런 그리디 문제는 우선순위 큐를 보통 사용해서 푼다

문제에서 요구하는 핵심은 최소로 강의실을 쓸 수 있는 개수이다

강의 A의 끝나는 시간이 강의 B의 시작 시간과 같거나 빠르면 그 강의 A가 끝나면 그 강의실에서 바로 B를 시작하면 된다. 그럼 강의실을 추가로 빌리지 않아도 됨

강의 B의 시작이 A보다 빠르면 A는 강의가 진행 중이므로 B는 새 강의실을 빌려야 한다

그래서 어떻게 접근했냐면 강의 정보를 강의 시작 시간의 오름차순으로 정렬 후 최소 우선순위 큐를 만들어 처음 강의가 끝나는 시간을 push했다

그럼 우선순위 큐의 top을 통해 가장 빨리 끝나는 강의의 끝나는 시간을 알 수 있다

그럼 반복문을 돌면서 현재 강의의 시작 시간과 우선순위 큐의 top을 비교해가면서 로직을 실행하면 되는 간단한 그리디 문제

코드

#include <bits/stdc++.h>
using namespace std;

int N;
struct Lecture
{
    int id;
    int start;
    int end;
};
vector<Lecture> lectures;

bool Compare(Lecture& l1, Lecture& l2)
{
    return l1.start < l2.start;
}

void Input()
{
    cin >> N;

}

void Solve()
{
    lectures.resize(N);

    for (int i = 0; i < N; i++)
    {
        int id, start, end;
        cin >> id >> start >> end;
        lectures[i] = { id, start, end };
    }

    sort(lectures.begin(), lectures.end(), Compare);

    priority_queue<int, vector<int>, greater<>> pq;
    pq.push(lectures[0].end);

    // pq의 size는 강의실의 개수와 같다

    for (int i = 1; i < N; i++)
    {
        // 가장 빨리 끝나는 강의의 끝나는 시간(pq)보다 현재 강의의 시작시간이 같거나 뒤이면 top을 빼고 현재 강의 push
        if (pq.top() <= lectures[i].start)
        {
            pq.pop();
            pq.push(lectures[i].end);
        }
        // 더 일찍 시작하면 그냥 push
        else
        {
            pq.push(lectures[i].end);
        }
    }

    cout << pq.size();
}

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

    Input();

    Solve();

    return 0;
}

// 2 14
// 3 8
// 6 20
// 6 27
// 7 13
// 12 18
// 15 21
// 20 25