[Greedy Algorithm] 수강 신청

def course_selection(course_list):
    # 여기에 코드를 작성하세요
    # 최종으로 수업을 담을 수 있는 리스트 생성
    early_time = []
    
    # 수업을 끝나는 순서대로 정렬
    sorted_list = sorted(course_list, key=lambda x: x[1]) # lambda x: 뒤에 인덱스 0, 1 조정
    
    # 가장 먼저 끝나는 수업은 무조건 듣는다
    early_time.append(sorted_list[0])
    
    # 이미 선택한 수업과 선택을 안한 수업 중 가장 빨리 끝나는 수업을 고른다.
    for i in sorted_list: 
        # 마지막 수업이 끝나기 전에 새 수업이 시작하면 겹친다.
        if i[0] > early_time[-1][1]:
            early_time.append(i)

    return early_time
        
        
    


# 테스트 코드
print(course_selection([(6, 10), (2, 3), (4, 5), (1, 7), (6, 8), (9, 10)]))
print(course_selection([(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]))
print(course_selection([(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 5), (13, 16), (9, 11), (1, 8)]))

해결과정
 
가장 먼저 끝나는 수업을 선택하는 것이 최적의 선택이다
1. course_list 가장 먼저 끝나는 순으로 정렬

# 먼저 시작하는 순으로 정렬
sorted_list = sorted(course_list, key=lambda x: x[0])

# 먼저 끝나는 순으로 정렬
sorted_list = sorted(course_list, key=lambda x: x[1])

# 짧은 순으로 정렬
sorted_list = sorted(course_list, key=lambda x: x[1] - x[0])

sorted 함수에 key 파라미터를 이용하면 원하는 기준으로 리스트를 정렬할 수 있다.
 
2. 이미 고른 수업이 끝나는 시간이 다른 수업이 시작하는 시간보다 늦으면, 두 수우업은 겹친다고 볼 수 있다.
 

시간 복잡도

 
course_list의 길이를 n이라고 하면 정렬시키는 부분의 시간 복잡도는 O(nlgn)이다.
그 후 반복문을 도는 부분은 O(n)
 
그럼 총 시간 복잡도는 O(nlgn+n)이기 때문에 결국 O(nlgn)이 된다.