[백준/Python] 1931번 - 회의실 배정

 

문제

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

 

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.

 

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

 

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

 

회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

 

 

입력

 

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

 

둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

 

시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

 

출력

 

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

 

풀이

 

주어지는 회의의 수가 많기 때문에 어떻게 풀까 생각하다가 회의가 끝나는 시간을 정렬한 뒤 리스트의 원소들을 순서대로 비교하면 회의의 수 만큼만 비교해도 되겠다는 생각이 들었다.

 

그래서 회의가 끝나는 시간을 기준으로 정렬한 뒤, i번째 회의의 시작시간이 이전에 시작한 회의의 끝나는 시간보다 크다면 cnt를 +1했다.

 

문제는 단순히 끝나는 시간을 기준으로만 정렬 했더니 시작시간이 정렬되지 않아서 만약 끝나는 시간이 같다면 시작시간을 기준으로 비교한 뒤 정렬하도록 코드를 짰다.

 

[풀이 요약]

1. 끝나는 시간을 기준으로 정렬하고, 만약 끝나는 시간이 같으면 시작 시간을 기준으로 시작시간이 더 늦은 것을 앞으로 가게 한다.
2. 리스트가 정렬되어 있으므로, 회의가 끝나는 시간보다 시작시간이 더 늦은 회의를 찾는다.
3. 시작시간이 더 늦은 회의를 찾으면 회의의 수를 +1 하고, 회의가 끝나는 시간을 새로 갱신한다.
4. 회의의 수를 return 한다. 

 

 

Code

 

 

import sys
input=sys.stdin.readline

def merge_sort(st,ed): # 정렬 함수
    if st>=ed :
        return [lst[st]]
    mid=(st+ed)//2
    l_lst=merge_sort(st,mid)
    r_lst=merge_sort(mid+1,ed)
    l_n=len(l_lst)
    r_n=len(r_lst)
    l,r=0,0
    re_lst=[]
    while l< l_n and r<r_n:
        if l_lst[l][1]<=r_lst[r][1]:
            if l_lst[l][1]==r_lst[r][1]: # 시작시간을 비교하도록 코드에 넣음
                if l_lst[l][0]<r_lst[r][0]:
                    re_lst.append(l_lst[l])
                    l += 1
                else:
                    re_lst.append(r_lst[r])
                    r += 1
            else:
                re_lst.append(l_lst[l])
                l+=1
        else:
            re_lst.append(r_lst[r])
            r+=1
    while l< l_n :
        re_lst.append(l_lst[l])
        l+=1
    while r<r_n:
        re_lst.append(r_lst[r])
        r+=1
    return re_lst

N=int(input())
lst=[list(map(int,input().split())) for _ in range(N)]
ans=merge_sort(0,N-1)
n_cnt=0
base=0
for i in range(N):
    if base<=ans[i][0]:
        base=ans[i][1]
        n_cnt+=1
print(n_cnt)

 

---

 

 

 

1931번: 회의실 배정