4) 수업 겹치지 않게 수강하기

4) 수업 겹치지 않게 수강하기

[(1, 2), (3, 4), (0, 6), (5, 7)]

튜플 앞 : 수업 시작시간

튜플 뒤 : 수업 종료시간

(0,6) 을 먼저 수강하기로 하면 다른 수업은 못 듣는다

풀이 (1)

def course_selection(course_list):
    course_list.sort()

    subject = [course_list[0]]

    for i in range(1, len(course_list)):
        if subject[0][1] > course_list[i][1]:
            subject = [course_list[i]]

    end = subject[0][1]

    for i in course_list[2:]:
        if end < i[0]:
            subject.append(i)
            end = subject[-1][1]

    return subject


# 테스트
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)]))

# 결과
 [(2, 3), (4, 5), (6, 8), (9, 10)]
 [(1, 2), (3, 4), (5, 7), (8, 9)]
 [(1, 3), (4, 7), (8, 10), (13, 16)]

풀이 (2)

def course_selection(course_list):
    # 수업을 끝나는 순서로 정렬한다
    sorted_list = sorted(course_list, key=lambda x: x[1])

    # 가장 먼저 끝나는 수업은 무조건 듣는다
    my_selection = [sorted_list[0]]

    # 이미 선택한 수업과 안 겹치는 수업 중 가장 빨리 끝나는 수업을 고른다
    for course in sorted_list:
        # 마지막 수업이 끝나기 전에 새 수업이 시작하면 겹친다
        if course[0] > my_selection[-1][1]:
            my_selection.append(course)

    return my_selection

# 테스트
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)]))

# 결과
 [(2, 3), (4, 5), (6, 8), (9, 10)]
 [(1, 2), (3, 4), (5, 7), (8, 9)]
 [(1, 3), (4, 7), (8, 10), (13, 16)]

풀이 (1)

풀이 (2)