코드

n = int(input())

time_table = []

for _ in range(n):
    time_table.append(list(map(int, input().split())))

def max_meeting_count(time_table):
    # 정답을 담을 변수
    result = 0
    
    # 이전 회의의 시작 시간을 담을 변수
    # 처음엔 0
    prev_meeting_end = 0
    
    # 회의가 빨리 끝날 수록 더 많은 회의가 진행될 수 있음
    # 종료 시간이 같은 경우, 빨리 시작한 회의가 우선
    time_table = sorted(time_table, key = lambda x: (x[1], x[0]))

    for i in time_table:
        start, end = i
        
        # 시작 시간이 이전 회의 종료시간보다 큰 경우
        # 회의가 시작됐다고 보면 됨
        if start >= prev_meeting_end:
            result += 1
            
            # 회의가 종료됐으므로
            # 해당 회의의 종료 시간을 
            # 이전 회의 시간을 담는 변수에 저장해줌
            prev_meeting_end = end
            
    return result

print(max_meeting_count(time_table))

문제 해설

그리디 알고리즘 참고

그리디 알고리즘 문제이다. 문제의 해결의 핵심은 회의가 종료되는 시간이 빠를 수록 진행할 수 있는 회의의 개수가 많아진다는 것. 이를 기준으로 1차적으로 정렬을 수행하고, 종료되는 시간이 같은 경우 시작 시간이 빠른 순서대로 정렬을 해준다.

time_table = sorted(time_table, key = lambda x: (x[1], x[0]))

첫 회의가 시작된 후, 다음 회의의 시작 시간이 직전의 회의 종료시간보다 값이 큰 경우 추가적인 회의가 진행되는 것이므로 값을 +1 해주고, 이전의 종료 시간을 현재 회의의 종료시간으로 업데이트한다.

이 과정을 일정의 수 만큼 반복 진행하면 정답이다.

댓글남기기

참고