백준 1931 회의실배정 (C++, Python)

www.acmicpc.net/problem/1931

1931번: 회의실배정

백준 1931 회의실배정 문제는 백준 11000 강의실 배정 문제와 함께 그리디 알고리즘 입문에 있어 반드시 겪고 넘어갈 문제라고 생각한다. 

---

[그리디 알고리즘]이란 매 순간, 가장 최선의 선택을 하는 것을 말한다.

이후에 따로 다시 정리하겠지만, 문제에서 어떠한 상황들(정점)이 어떻게 서로 연결되어지고 관계를 맺는지(간선)를 파악하는 것이 매우 중요하다. 어찌 보면 가장 중요하다고도 볼 수 있을 것 같다.

 

• 하나의 정점(상황)에서 일정한 규칙에 의해서 다음 정점 또는 정점들로 이동한다면 DP(Dynamic Programming, 동적 계획법)을 사용할 수 있고, 
• 하나의 정점에서 연결된 이웃 정점들로만 갈 수 있다면 트리, 그래프 등의 비선형 구조 문제인 것으로 생각해 볼 수 있으며,
• 하나의 정점에서 일정한 처리를 한 후, 원복하여 다시 돌아간다면 백트래킹,
• 확인할 정점들을 범위로 나누어 확인하거나 합칠 경우, 이분 탐색 또는 분할 정복,
• 그리고 이번 문제처럼, 단지 매 정점에서 항상 최선의 선택만 한다면, 그리디 알고리즘 문제라고 볼 수 있다.

위와 같이, (내가 이해하기엔) 한 정점에서 어떤 판단을 하느냐가 문제를 풀어내는 방법을 결정하는 중요한 요소이며, 그에 따라 어떤 자료구조, 알고리즘을 적용할 수 있는지가 결정된다.

---

 

이 문제와 강의실 배정 문제와의 차이점은 강의실 배정 문제는 강의실을 계속 새로 생성하지만, 이 문제는 하나의 회의실 안에 최대 개수의 회의를 열어야 한다는 점이다. 이 문제에서 정점은 첫 번째 회의가 시작하는 시점, 각 회의를 마친 시점이 될 것이며, 간선은 다음 회의와의 연결 가능성 등으로 (추상적) 이해가 가능하다. 여러 정점(회의정보)들이 여기저기 흩어져있고, 정점들 간의 간선(연결되는 회의들)은 주어지지 않았다. 그렇다고 정점과 정점간 연결 규칙성(다음 회의는 반드시 30분후에 시작 등과 같은 규칙)이 있는 것도 아니다. 그저 하나의 정점에서(회의를 마친 후), 현재 상황에서 어떤 정점이 그 다음 차례로 최적인지 매번 최선의 선택을 해야하는 것이다. (-> 그리디)

 

"가장 일찍 시작하는 회의부터 채워야 하지 않을까?"

"가장 회의시간이 짧은 회의들 위주로 채워야 하지 않을까?"

"가장 일찍 끝나는 회의 위주로 채워야 하지 않을까?"

 

위와 같은 질문들을 머릿속에 떠올릴 수 있으며, 저 중 하나가 각 정점에서 다음 정점으로 가는 방법이 된다. 조금만 더 생각해보면, 마지막 질문 "가장 일찍 끝나는 회의..."가 가장 적합하다는 사실을 알 수 있다. 왜냐하면 가장 일찍 끝나는 회의가 위의 2가지 다른 질문 내용을 한꺼번에 만족시키기 때문이다. 결국 일찍 끝나는 회의가 회의시간도 짧은 편이었고, 더 일찍 시작했을 것이다.

 

따라서 주어진 회의시간표에서 일찍 끝나는 회의 순으로 1차 정렬하고, 동일 종료 시각을 갖는 회의들에 대해 일찍 시작하는 순으로 2차 정렬하면, 문제 해결에 대한 준비가 끝난다. 이후, 다음 회의가 이전 회의 종료시각과 같거나 늦은 시각에 시작한다면 그 회의를 이어서 넣을 수 있는 것이다.

 

<주요 내용>

그리디 알고리즘, 정렬

 

<코드>

C++에서는 커스텀 비교 함수를 만들고, 퀵 소트를 연습해보았다. 파이썬 코드는 STL heapq를 사용했다.

#include <iostream>
#include <cstdio>
#include <stdlib.h> //qsort
using namespace std;

struct Meeting
{
    int time[2];
};

int cmp(const void *p1, const void *p2)
{
    Meeting *a = (Meeting *)p1;
    Meeting *b = (Meeting *)p2;
    int diff = a->time[1] - b->time[1];
    // return diff;
    if (diff)
        return diff;
    return a->time[0] - b->time[0];
}

int n, temp0, temp1;
Meeting givenTime[100000];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)cin>>givenTime[i].time[0]>>givenTime[i].time[1];
    qsort(givenTime, n, sizeof(Meeting), cmp);
    int prevMtEnd = 0;
    int count = 0;
    int i = 0;

    while (i < n)
    {
        if (givenTime[i].time[0] >= prevMtEnd)
        {
            count++;
            prevMtEnd = givenTime[i].time[1];
        }
        i++;
    }
    cout << count << endl;
}

 

import sys
import heapq
si = sys.stdin.readline


def main():
    n = int(si())
    pq = []
    while n:
        n -= 1
        [a, b] = [int(e) for e in si().split()]
        heapq.heappush(pq, (b, a))

    cnt, prv = 0, -1
    while pq:
        curr = heapq.heappop(pq)
        if curr[1] >= prv:
            cnt += 1
            prv = curr[0]
    print(cnt)


if __name__ == '__main__':
    main()