Baekjoon 1931번 회의실배정

문제

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

걸린 시간

03 : 13 : 42

풀이

Python3

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())

    info = {}

    for _ in range(0, N):
        s, e = map(int, input().split())

        # 시작시간이 딕셔너리에 없으면
        if info.get(s, -1) == -1:
            # 키와 값 쌍을 추가
            info[s] = [e]

        # 딕셔너리에 존재하면
        else:
            info[s].append(e) 

    # 딕셔너리 키 값을 기준으로 오름차순 정렬
    key = sorted(info)

    l_s = l_e = 0
    count = 0

    for i in range(0, len(key)):
        s = key[i] 
        li = info.get(s, -1)
        li.sort()
        for j in li:
            e = j

            # 다음으로 오는 시작시간이 가장 최근의 종료시간보다 크거나 같을 경우 
            if l_e <= s:
                count += 1
                l_s = s
                l_e = e

            # 다음으로 오는 종료시간이 가장 최근의 종료시간보다 작거나 같고, 회의 시간이 가장 최근의 회의 시간보다 작거나 같을 경우
            elif l_e >= e and l_e-l_s >= e-s:
                # 다음으로 오는 시작, 종료 시간을 가장 최근으로 설정함.
                l_s = s
                l_e = e

    print(count)

문제를 어떻게 풀어야 할지 떠오르지 않아 규칙을 찾는데만 한시간이 걸렸다.

또 시작시간과 종료시간이 같을 경우의 처리를 해주지 않아 이를 해결하는데도 시간이 오래 걸렸다.

그래도 정답을 보지않고 문제의 의도대로 탐욕 알고리즘을 구현했다는 점이 뿌듯하다.

C++

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm> // sort
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<pair<int, int>> table;
    int s, e; // start, end
    for(int i = 0; i < n; i++){
        cin >> s >> e;
        table.push_back(make_pair(e, s));
    }
    // greedy
    sort(table.begin(), table.end());
    e = table[0].first;
    s = table[0].second;
    int ans = 1;
    for(int i = 1; i < n; i++){
        int end = table[i].first;
        int start = table[i].second;
        // 시작시간이 이전 회의의
        // 종료시각보다 이르다면
        if(e > start) continue;
        s = start;
        e = end;
        ans++;
    }
    cout << ans << "\n";
    return 0;
}