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

그리디 알고리즘 공부하려고 풀었던 문제

 

문제 링크 : 1931 회의실 배정

 

문제 정리: 

한 개의 회의실에서 최대 몇 개의 회의를 진행할 수 있는가?

 

조건 : 

• 각 회의가 겹치면 안된다.
• 회의는 중간에 중단될 수 없다.
• 회의가 끝나면 바로 다음 회의를 진행할 수 있다.
• 회의 시작 시간과 종료 시간이 동일할 수 있다.

풀이 방법 :

1. 시작 시간을 정렬을 해야하고, 끝나는 시간 기준으로 정렬을 해야한다.
   (최대 값을 구해야하기 때문에, 빨리 끝나는 회의를 위주로 최대한 많이 집어 넣어야하기 때문)
2. 끝나는 시간을 기준으로, 다음 인덱스에 시작 시간을 비교하여 answer를 작업한다.

def solution(conference):
    last = 0
    answer = 0
    for start, end in conference:
        if start >= last:
            answer += 1
            last = end

    return answer

if __name__ == '__main__':
    N = input()
    conference_list = []

    for i in range(int(N)):
        start, end = input().split()
        conference_list.append((int(start), int(end)))

    conference_list.sort(key=lambda x:x[0])
    conference_list.sort(key=lambda x:x[1])
    answer = solution(conference_list)
    print(answer)

 

풀이하는데는 대력 20분 안쪽으로 걸렸던 것같다.

처음에 시작 시간만 가지고 정렬을 하려고 했어서, 이중 for문으로 하나하나 다 비교해야하나 생각했는데,

끝나는 시간 기준 정렬을 추가했더니 해결 완료!