11000 강의실 배정

11000. 강의실 배정 / c++ / Gold 5 / 40분 / 461등

문제

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

1. 강의의 시작시간과 종료시간이 주어진다.
2. 강의들이 겹치지 않으면 같은 강의실에서 들을 수 있다.
3. 강의실을 최소한으로 사용했을 때 그 수는?

접근 방식

그리디, 우선순위 큐, 라인 스위핑

1. 처음엔 어렵게 생각해서, 해당 강의실의 강의가 끝나는 시간과 가장 가까운 시간의 다음 강의를 붙여야 한다고 생각했다.
2. 하지만 그럴 필요가 없었다. 이런건 line sweeping 알고리즘이 같이 사용된다.
3. 시작 시간을 기점으로, 빨리 시작하는 순으로 정렬해놓고 순회하면서, 우선순위 큐에 끝지점을 넣게된다.
4. 즉, 지금 내가 처리할 강의는 남은 강의 중 ‘가장 빨리 시작하는 강의’이고, 내가 우선순위 큐에서 뽑은 강의는 처리한 강의 중 ‘가장 빨리 끝나는 강의’인 것이다.
5. 이 둘을 비교했을 때, 시작시간이 끝나는 시간보다 이르다면, 새로운 강의실 하나가 필요한것이고
6. 시작시간이 끝나는 시간과 같거나, 더 늦다면, 해당 강의실에서 진행할 수 있게되는 것이다. (우선순위 큐에서 pop)

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int N, S, T;
vector<pair<int, int>> v;
priority_queue<int, vector<int>, greater<int>> rooms;

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

    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        cin >> S >> T;
        v.push_back({ S, T });
    }

    sort(v.begin(), v.end(), [](pair<int, int> A, pair<int, int> B)->bool {
        if (A.first == B.first) return A.second < B.second;

        return A.first < B.first;
        });

    
    rooms.push(v[0].second);
    for (int i = 1; i < v.size(); ++i)
    {
        if (rooms.top() <= v[i].first)
        {
            rooms.pop();
        }
        rooms.push(v[i].second);
    }

    cout << rooms.size() << '\n';

    return 0;
}

다시 생각해 볼 점

1. 메모리를 줄여보려고, 배열에 넣고 정렬했던 부분을 우선순위 큐를 사용해봤는데, 오히려 메모리가 더 늘었다.
2. 그리디 = 우선순위 큐, 항상 기억하자.
3. 문제를 어렵게 (혹은 제대로 이해하지 못하는 경우) 보지 말자.
4. 그리디는 내가 현재 처리하는 값이 항상 ‘남은 것 중 제일 ~~한 값’이라는 점을 명심하자.