백준 11000 강의실 배정 (C++, 파이썬)

www.acmicpc.net/problem/11000

11000번: 강의실 배정

백준 1931 회의실배정 문제와 함께 풀어보아야 할 기본적인 그리디 알고리즘 문제라고 생각한다. 이 문제는 계속 강의실을 새로 개설할 수 있고 몇 개의 강의실이 필요한지를 구한다는 점에서 다르다.

 

바로 풀이내용부터 설명하면,

우선순위 큐를 2개 사용하여, 하나에는 강의시간표를 담고 (시작시간 오름차순), 다른 하나에는 보유하고 있는 강의실 목록 (종료시간 오름차순)을 담으면 된다. 이처럼 정렬을 통해 기본적인 문제 설정 몇 가지를 해결하고, 가장 일찍 시작하는 강의부터 체크해 나가면 된다.

 

그리고, 당연히 처음에는 아무런 강의실이 없으므로 첫번째 강의를 위한 새로운 강의실을 만들어 준다.

그리고 다음부터 들어오는 강의는 아직 시작하지 않은 강의들 중 가장 일찍 시작하는 강의일 것이고, 그것을 현재 보유하고 있는 강의실들 중 가장 일찍 끝나는 강의실의 종료시간과 비교해주는 것이다. 

 

참조 그림1

위의 참조 그림1에서와 같이, 4개의 강의실이 있고 각각의 종료되는 시각이 있을 때 11시에 시작하는 새로운 강의가 들어왔다고 예를 들어보자. 9시와 10시에 종료하는 강의실이 2개나 있고, 11시가 되는 시점에는 2개의 강의실이 비어있을 테니, 새로운 강의실을 만들 필요가 없다. 그렇다면 이제 저 새로운 강의는 어떤 강의실에서 열려야 하는 걸까?라는 의문이 생길 수 있다.

 

위의 그림에서처럼 주황색 화살표가 가리키는 오전9시에 끝난 강의실을 사용할지 아니면, 빨강색이 가리키는 강의실을 사용할 지라는 의문.

그 의문에 대한 대답은 '어디서 하든 상관없다'이다. 왜냐하면 이 11:00강의(A라고 명명) 다음에 오는 강의(B라고 명명)는 11:00과 같거나 더 늦게 시작하는 강의일 테고, 그 B강의가 시작할 때는 적어도 하나의 빈 강의실이 있을 것이기 때문이다.

A가 시작할 때 2개의 빈 강의실이 있었다면, 그 2개의 빈 강의실은 11:00와 같거나 더 일찍 끝난 강의실이었을 테고,

그다음 B강의는 반드시 A와 같거나 늦게 시작하기에, A가 어디를 선택했더라도 B는 적어도 하나의 빈 강의실은 갖게 된다.

 

이 사실 덕에, 다음 강의의 시작시간은 항상 보유 강의실들 중 가장 일찍 끝난 시간 하고만 비교하면 된다. 단 한 번의 비교로 강의실을 새로 만들어야 하는지를 판단할 수 있게 된 것이다.

이것이 정렬을 통해 얻는 이득이다. 이미 정렬이 되었기에 다음 강의가 모든 강의실 시간을 전부 확인할 필요가 없는 것이다.

매 강의때마다 모든 강의실을 체크해야 한다면 O(n^2)의 시간복잡도를 갖겠지만, 정렬을 통해 O(n log n)으로 해결되는 것이다.

 

문제 해결을 위해서 중요한 것은 아니지만, 'i번째 수업이 어떤 강의실을 선택할지 고민할 때, 그 수업이 들어갈 수 있는 강의실이 m개 있었다면, 적어도 현 i번째 수업을 포함하여 다음 m개의 수업은 새로운 강의실이 필요하지 않다'는 사실도 같이 알 수 있다.

 

<주요 내용>

우선순위 큐, 그리디 알고리즘

 

<코드>

C++코드는 퀵 소트, 구조체, 포인터 연습을 하느라, 조금 다른 길로 돌아갔다. 파이썬 코드는 위의 설명과 같이 우선순위 큐 2개를 사용했다.

#include <iostream>
#include <stdlib.h>  //qsort
#include <algorithm> //sort
#include <queue>
using namespace std;

priority_queue<int,vector<int>,greater<int>> pq;
int n, s, t, room = 0;
struct lecture
{
    int time[2];
};
typedef struct lecture lecture;
struct lecVec
{
    int pos;
    lecture *arr;
};
typedef struct lecVec lecVec;
void initLec(lecVec *l, int n)
{
    l->pos = 0;
    l->arr = new lecture[n];
}
int cmp(const void *p1, const void *p2)
{
    lecture *a = (lecture *)p1;
    lecture *b = (lecture *)p2;
    int diff = a->time[0] - b->time[0];
    if (diff)
        return diff;
    else
        return a->time[1] - b->time[1];
}

int main()
{
    cin >> n;
    lecVec *table = new lecVec;
    initLec(table, n);
    lecture *arrLec = table->arr;

    for (int i = 0; i < n; i++)
    {
        cin >> s >> t;
        (arrLec + i)->time[0] = s;
        (arrLec + i)->time[1] = t;
        table->pos++;
    }
    qsort(table->arr, n, sizeof(lecture), cmp);

    for (int i = 0; i < n; i++)
    {
        if (!pq.empty())
        {
            if (pq.top()<=(arrLec+i)->time[0]) pq.pop();
        }
        pq.push((arrLec+i)->time[1]);
    }

    cout<<pq.size()<<endl;
    delete[] table->arr;
    delete table;
}

 

import sys
import heapq
si = sys.stdin.readline


def main():
    cnt, n, pq, rooms = 1, int(si()), [], []
    for _ in range(n):
        [a, b] = [int(e) for e in si().split()]
        heapq.heappush(pq, (a, b))

    heapq.heappush(rooms, heapq.heappop(pq)[1])
    while pq:
        curr = heapq.heappop(pq)
        if curr[0] < rooms[0]:
            cnt += 1
        else:
            heapq.heappop(rooms)
        heapq.heappush(rooms, curr[1])
    print(cnt)


if __name__ == '__main__':
    main()