[Algorithm] Softeer 강의실 배정 - Lv.3 (python)

[ Softeer 연습문제 - 강의실 배정 ]

• 문제명 : 강의실 배정 - (Level.3)
• 사용언어 : python
• 알고리즘 : 그리디 알고리즘

---

 문제

김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다.

 

 

알고리즘 및 풀이

: 최대 가치를 계산하는 그리디 알고리즘을 활용하여 풀었다.

이 문제에서는 강의 list를 종료 시간을 기준으로 정렬 하는 것이 포인트인 것 같다.

각 강의가 종료되는 시간을 기준으로 정렬한 뒤,

현재 시간과 겹치지 않는 강의 중에서 가장 빨리 끝나는 강의를 선택하는 방식으로 접근했다.

 

import sys

def maximize_lectures(lectures):
    # 종료 시간을 기준으로 정렬
    lectures.sort(key=lambda x : x[1])
    
    #현재 시간과 선택된 강의 수 초기화
    now_t = 1
    selected_lectures = 0
    
    # 강의 리스트 순회
    for start, end in lectures:
    	# 현재 강의와 겹치지 않는 경우 선택
        if now_t <= start:
            now_t = end
            selected_lectures += 1

    return selected_lectures


# 입력 받기
N = int(input())
lectures = [list(map(int, input().split())) for _ in range(N)]

# 최대 강의 수 출력
result = maximize_lectures(lectures)
print(result)

 

  결과