211123 - 회의실 배정

◾ 회의실 배정

문제

회사에 급한 일이 생겨 많은 팀이 회의하게 되었습니다. 하지만 회의실은 1개밖에 없으므로 관리팀은 가능한 많은 팀이 회의할 수 있는 경우를 골라 그 팀들에게 회의실을 빌려주기로 하였습니다. 각 팀은 회의 시작 시각과 종료 시각을 적어 제출하였고, 편의상 한 팀이 회의를 종료하고 나가 다음 팀이 회의를 준비하는 시간은 0으로 가정합니다. 또한, 회의의 시작시간과 끝나는 시간이 같을 수도 있습니다.

각 팀이 제출한 회의 시작 시각과 종료 시각이 arr(배열)로 주어질 때, 회의를 할 수 있는 최대 팀의 개수를 반환하는 solution 함수를 완성하세요.

---

입력

• 회의 일정 목록 개수 : 100,000이하의 자연수
• 회의 시작 시각(S), 종료 시각(E) 범위 : 0 <= S <= E <= 20,000,000

출력

• 회의를 할 수 있는 최대 팀의 개수

입출력 예

arr	result
[[1, 2], [2, 4], [2, 2]]	3
[[1, 4], [2, 6], [4, 7	2

---

◾ 풀이

1. 해설

• 회의 종료 시각을 기준으로 오름차순 정렬하여 가능한 회의의 개수를 확인한다.
• 가능한 회의는 이전 회의 종료 시간보다 시작 시간이 크거나 같으면 가능하다.
  • 회의 : [[1, 2], [2, 2], [2, 4]]
  • 마지막 종료 시간 : 0 => [1, 2] : 가능
  • 마지막 종료 시간 : 2 => [2, 2] : 가능
  • 마지막 종료 시간 : 2 => [2, 4] : 가능
  • 총 3개의 회의 가능

---

2. 프로그램

1. arr 종료 시각, 시작 시각 순으로 정렬
2. 각 회의마다 가능한 회의인지 조사
   • start >= last 인 경우 가능한 회의
   • 가능한 회의이면 last 변경

# 코드
def solution(arr):
    answer = 0
    # 종료 시각을 기준으로 각 원소 정렬
    arr.sort(key = lambda x : (x[1], x[0]))
    last = 0    # 마지막 종료 시간

    # 각 회의에 따라 가능한지 조사
    for start, end in arr:
        # 시작 시간이 마지막 종료 시간 이상이라면 가능한 회의
        if start >= last:
            last = end  # 마지막 종료 시간 변경
            answer += 1 # 가능한 회의 개수 추가

    return answer