백준 1931 회의실 배정 Python 3

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

1931번: 회의실 배정

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1931.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def get_maximum_cnt(N, meetings):
    start = meetings[0][0]
    end = meetings[0][1]
    cnt = 1
    for i in range(1, N):
        if end > meetings[i][1]:
            start = meetings[i][0]
            end = meetings[i][1]
        elif end <= meetings[i][0]:
            cnt += 1
            start = meetings[i][0]
            end = meetings[i][1]
    print(cnt)

input = sys.stdin.readline
N = int(input())
meetings = list()
for _ in range(N):
    meetings.append(list(map(int, input().split())))
meetings.sort()
get_maximum_cnt(N, meetings)

---

풀이 과정

풀이 시간 37분

1개의 회의실에 N개의 회의를 배정해야 한다.

이때 각 회의마다 시작시간과 끝나는 시간을 알 수 있고, 각 회의가 겹치지 않게 배정해야 한다.

한 회의가 끝남과 동시에 다음 회의가 시작될 수 있고, 회의의 시작시간과 끝나는 시간이 같을 수 있다.

N개의 회의 중 회의실을 사용하는 회의의 최대 개수를 구해보자.

 

회의를 고르는 순간마다 최대 개수를 만들어가면서 골라나가면 정답을 구할 수 있다.

즉, 그리디 알고리즘을 적용할 수 있다.

나는 먼저 회의의 시작시간을 기준으로 회의들을 정렬하고 순차적으로 탐색하면서 해당 회의를 선택할지 말지를 결정하도록 알고리즘을 짰다.

import sys
def get_maximum_cnt(N, meetings):
	#가장 처음 시작하는 회의를 선택한 것으로 초기화 한다
    start = meetings[0][0]
    end = meetings[0][1]
    cnt = 1
    
    #두번째 회의부터 순차적으로 탐색하며 회의실을 사용할 회의를 선택해나간다
    for i in range(1, N):
    	#i번째 회의가 이전 회의보다 먼저 끝나는 경우, 이전 회의는 취소하고 i번째 회의를 선택한다
        if end > meetings[i][1]:
            start = meetings[i][0]
            end = meetings[i][1]
            
        #i번째 회의가 이전 회의보다 늦게 끝나고, 이전 회의가 끝난 뒤에 i번째 회의가 시작되는 경우,
        elif end <= meetings[i][0]:
        	#i번째 회의를 추가한다
            cnt += 1
            start = meetings[i][0]
            end = meetings[i][1]
            
    print(cnt)

input = sys.stdin.readline
N = int(input())
meetings = list()
for _ in range(N):
    meetings.append(list(map(int, input().split())))
    
#회의의 시작시간을 기준으로 오름차순 정렬
meetings.sort()
get_maximum_cnt(N, meetings)

#시간복잡도 = O(N), 공간복잡도 = O(N)