Home [11000] 강의실 배정
Post
Cancel

[11000] 강의실 배정

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

11000 - 강의실 배정

본문

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

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

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

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

입력

첫 번째 줄에 N이 주어진다. (1N200000)

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

출력

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

제한

시간 제한메모리 제한
1sec256MB

풀이

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

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

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

코드

사용 언어 : C

최종 수정일 : 2024 / 5 / 30

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#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;
}
This post is licensed under CC BY 4.0 by the author.