[11000] 강의실 배정

문제 링크 : https://www.acmicpc.net/problem/11000

11000 - 강의실 배정

본문

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

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

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

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

입력

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

이후 $N$개의 줄에 $S_i, T_i$가 주어진다. ($0 \leq S_i < T_i \leq {10}^9$)

출력

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

제한

시간 제한	메모리 제한
1sec	256MB

---

풀이

모든 수업을 배정하기 위한 최소 강의실의 개수를 구하는 문제이다. 강의실에 수업을 하나하나 넣어보면 쉽게 해결할 수 있는 문제이다. 수업이 끝나면 그 강의실은 비워둔 채로 있다가, 다른 수업이 시작한다하면 빈 강의실에 배정하면 된다. 만약 모든 강의실에서 수업 중이라면 강의실은 하나 더 만들어서 배정하면 된다. 빈 강의실은 없어지지 않으므로, 결과적으로는 새로 만들어진 강의실의 개수를 세면 될 것 같다.

배열을 통해 문제를 해결할 수 있다. 배열의 칸들을 각각 하나의 강의실로 생각하고, 수업이 끝나 빈 강의실에 새로운 수업을 넣으면 된다. 수업을 넣어야 하는데 빈 강의실이 없다면 배열의 칸을 하나 늘리는 것으로 강의실을 만들어낼 수 있다. 그렇게 한다면 최종적으로 만들어진 배열의 길이가 문제에서 원하는 답이 된다. 문제는 강의실의 관리이다. 수업이 끝난 시간마다 강의실을 비워야하고, 빈 강의실을 찾아가는 과정 또한 배열 탐색을 거쳐야하므로 $O(N)$이 걸린다. 심지어 시간의 범위는 $10^9$이므로 일반적인 탐색으로는 불가능하다. 이는 시간 압축을 통해 해결할 수 있다지만, 1차원 배열로만 관리하는 것에는 제약이 있을 수밖에 없다.

이 점은 우선순위 큐를 이용하면 문제를 쉽게 해결할 수 있다. 강의실을 만들어야할 상황이라면 결과값에 $1$을 추가하고, 빈 강의실을 찾는 방법은 “현 시점에서 수업이 끝난 강의실이 있는가“를 찾아내면 되는 것이다. 이는 우선순위 큐를 수업이 끝나는 시간 오름차순으로 놓는 것이다. 그리고 수업을 강의실에 배정할 때에만 이미 수업이 끝난 빈 강의실을 하나 찾아 들어가도록 유도하는 방법으로 구현하면 위에서 말했던 문제점들을 해결할 수 있게 된다.

• 참고 알고리즘 : 우선순위 큐

코드

사용 언어 : C

최종 수정일 : 2024 / 5 / 30

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

typedef struct Class {
    int s, e;
} CS;

#define MAX_IDX 200000
const int NONE = -1;

int cmp(CS* a, CS* b) {
    if (a->s != b->s) {
        return a->s > b->s;
    } else {
        return a->e > b->e;
    }
}

int n;
CS arr[MAX_IDX];

int priority_queue[2 * MAX_IDX + 10];
int top = 0;

void insert(int x) {
    priority_queue[++top] = x;
    int i = top;

    while (i != 1 && x < priority_queue[i / 2]) {
        int a = priority_queue[i / 2];
        priority_queue[i / 2] = x, priority_queue[i] = a;
        i /= 2;
    }
    return;
}

int pop() {
    if (top == 0) {
        return 0;
    }

    int retval = priority_queue[1];
    priority_queue[1] = priority_queue[top--];

    int i = 1, tp = 2;
    while (tp < top) {
        tp += (priority_queue[tp] > priority_queue[tp + 1]);
        if (priority_queue[i] <= priority_queue[tp]) {
            break;
        }

        int a = priority_queue[tp];
        priority_queue[tp] = priority_queue[i], priority_queue[i] = a;

        i = tp, tp *= 2;
    }
    if (tp == top && priority_queue[i] > priority_queue[tp]) {
        int a = priority_queue[tp];
        priority_queue[tp] = priority_queue[i], priority_queue[i] = a;
    }

    return retval;
}

int head() {
    if (top == 0) {
        return NONE;
    } else {
        return priority_queue[1];
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        arr[i] = (CS){a, b};
    }
    qsort(arr, n, sizeof(CS), cmp);

    int retval = 1;
    insert(arr[0].e);

    /* solve() */
    for (int i = 1; i < n; ++i) {
        if (arr[i].s < head()) {
            ++retval;
        } else {
            pop();
        }

        insert(arr[i].e);
    }

    printf("%d", retval);
    return 0;
}