[AlgorithmSolving][Greedy] JUNGOL_1370: 회의실 배정

1. 문제 내용

• 문제:

  회의실이 하나 있다. 여러 회의들이 시작시간과 종료시간이 예약되어 있으며, 시간대가 겹치는 회의는 동시에 개최가 불가능하다. 

  따라서 같은 시간대에 속하는 회의들 중 하나만 개최하고 나머지 회의들은 버려야한다. 

  단, 종료시간과 시작시간이 같은 경우에는 시간이 겹친다고 말하지 않는다. 

  회의의 개수 N과 각 회의의 시작시간, 종료시간이 주어졌을 때 되도록 많은 회의를 개최하고자 한다.

  회의를 최대한 많이 배정하는 프로그램을 작성하시오.​

• 입력:

  첫줄에는 회의의 수 N(5≤N≤500)가 주어진다.

  다음 N줄에 걸쳐, 각 회의의 번호와 시작시간과 종료시간이 차례로 주어진다. (500 이하의 자연수)

  한 회의에서 시작시간과 종료시간이 같은 경우 및 여러 회의의 번호가 서로 같은 경우는 주어지지 않는다.

• 출력:

  첫줄에는 배정 가능한 최대의 회의수를 출력하고 다음 줄부터는 배정한 회의의 번호를 시간대순으로 출력한다.

  만약, 답이 여러 가지(최대회의수가 될 수 있는 배정 방법이 여러가지)라면 그 중 아무거나 하나 출력한다.

• 입력 예제:

  6
  1 1 10
  2 5 6
  3 13 15
  4 14 17
  5 8 14
  6 3 12
  

• 출력 예제:

  3
  2 5 4
  

2. 문제 유형 파악

이 문제는 탐욕(Greedy) 알고리즘의 가장 클래식하고 대표적인 유형인 “활동 선택 문제(Activity Selection Problem)” 또는 “스케줄링 문제”입니다.

하나의 회의실(한정된 자원)에 최대한 많은 회의(활동)를 배정해야 하므로, “현재 시점에서 어떤 회의를 선택하는 것이 가장 많은 회의를 열 수 있는가?”를 탐욕적으로 결정해야 합니다.
입력 제한을 보면 회의의 수 N이 최대 500입니다. 따라서 모든 경우의 수를 확인하는 방식 대신, 배열을 특정 기준에 따라 정렬한 뒤 순회하는 O(N log N) 시간 복잡도의 그리디 알고리즘을 사용하면 아주 넉넉하게 통과할 수 있습니다.

3. 문제를 풀기 위한 핵심 아이디어

이 문제를 관통하는 유일하고도 가장 중요한 핵심은 “회의를 어떤 기준으로 정렬할 것인가?”입니다. 이 기준만 제대로 잡으면 문제는 90%이상 풀린 것과 다름없습니다.

1. 정렬의 절대 기준은 “종료 시간”이다.

최대한 많은 회의를 배정하기 위해서는 회의가 “무조건 일찍 끝나야”합니다. 회의가 일찍 끝날수록 남은 빈 시간이 길어지고, 그 자리에 다른 회의를 하나라도 더 욱여넣을 수 있는 기회가 생기기 때문입니다.

따라서 입력받은 회의 정보들을 “종료 시간이 빠른 순서대로” 오름차순 정렬하는 것이 가장 첫 번째 단계이자 핵심 아이디어입니다. (만약 종료 시간이 같다면, 시작 시간이 빠른 순서로 정렬해야 합니다 .)

1. 왜 다른 기준ㅇ르 쓰면 안 될까? (반례 확인)

그리디 알고리즘의 정당성을 확인하기 위해, 머릿속으로 “시작 시간”이나 “회의 진행 시간”을 기준으로 잡았을 때의 반례를 떠올려 보아야 합니다.

- [실패하는 기준1] 시작 시간이 빠른 순서로 정렬한다면?
  - 반례: 아침 9시에 시작하지만 끝나는 시간이 밤 10시인 회의가 있다고 가정해 봅시다. 시작 시간이 가장 빠르다는 이유로 이 회의를 선택해 버리면, 중간에 열릴 수 있었던 짧은 회의 10개를 모두 날려버리게 됩니다.

- [실패하는 기준2] 회의 진행 시간이 짧은 순서로 정렬한다면?
  - 반례: 
    다음과 같이 3개의 회의가 있습니다.   
    (A) 09:00 ~ 12:00   
    (B) 11:00 ~ 13:00 (진행 시간 2시간으로 가장 짧음)
    (C) 12:00 ~ 15:00
  - 가장 짧은 (B)를 선택해 버리면 시간이 겹치는 (A)와 (C)를 모두 포기해야 해서 총 1개의 회의만 열 수 있습니다. 반면, (A)와 (C)를 선택하면 총 2개의 회의를 열 수 있습니다.

따라서 위의 두 기준은 탐욕적 선택 속성을 만족하지 못하며, 오직 “종료 시간이 가장 빠른 것”을 고르는 것만이 무조건적인 최적해를 보장합니다.

1. 순회하며 회의 배정하기 (상태 업데이트)

정렬이 완료되었다면, 이제 맨 앞에서부터 차례대로 배열을 순회하며 다음 과정을 반복합니다.

1. 정렬된 배열의 첫 번째 회의는 무조건 개최합니다. (종료 시간이 가장 빠르기 때문입니다.)
2. 현재 개최 중인 회의의 "종료 시간"을 변수(예: `last_end_time`)에 기록합니다.
3. 다음 회의를 검사할 때, 그 회의의 "시작 시간"이 `last_end_time` 보다 크거나 같다면, 시간이 겹치지 않으므로 해당 회의를 개최하고, `last_end_time`을 새로운 회의의 종료 시간으로 갱신해 줍니다.

이 과정을 배열의 끝까지 단 한 번만 순회하면 정답을 도출할 수 있습니다.

4. 코드

import sys

def solve():
    input = sys.stdin.readline

    n = int(input())

    meeting_list = [tuple(map(int, input().split())) for _ in range(n)]

    meeting_list.sort(key=lambda x:x[2])

    result_list = []
    current = 1

    for i in range(n):
        if meeting_list[i][1] >= current:
            result_list.append(meeting_list[i][0])
            current = meeting_list[i][2]

    print(len(result_list))
    print(" ".join(map(str, result_list)))

solve()