[Python] 1931 - 회의실 배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

• 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

• 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

• 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

• 첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

---

풀이

• 총 3번의 시도(==갈아업기)를 통해 답을 받았다.

• 덕분에 비트마스크를 공부할 수 있었다.👍

• sort(key=lambda)는 정렬에서 절대 잊어서는 안될 함수다.

시도 1

• 회의 시간이 짧은 순으로 정렬을 하고 비트마스킹을 사용해 풀었다. ❌
  • 당연히 회의가 짧으면 더 많이 할 수 있다고 생각했는데 아래와 같은 반례가 있다.
  • 주황색 박스가 속한 위쪽 라인은 2번의 회의를 할 수 있지만, 아래쪽 라인은 총 3번의 회의가 가능하다.

    

    반례 1

시도 2

• 시작 시간이 빠르순으로 정렬하고 종료 시간이 빠른순으로 다시 정렬해 풀었다. ❌
  • 이건 백준에 있는 예제가 곧 반례가 된다.
  • 예제를 보면 (1, 4)부터 사용하면 4번의 회의를 할 수 있지만, 시작 시간 빠른 순으로 (0, 6)부터 사용하면 3번의 회의 밖에 못한다.

    (0, 6) → (8, 11) → (12, 14)

    

시도 3

• 종료 시간이 빠른순으로 정렬하고 시작 시간이 빠른순으로 다시 정렬해 풀었다. ✅
  • 결국 빨리 회의가 끝나야 더 많은 다음 회의를 할 수 있다는 결론을 내렸다.

답

import sys

input = sys.stdin.readline


def assignroom(m):
    cnt = 0
    last = 0
    m.sort(key=lambda time: (time[1], time[0]))
    for meet in m:
        if last <= meet[0]:
            cnt += 1
            last = meet[1]
    return cnt


if __name__ == "__main__":
    N = int(input())
    meeting = [list(map(int, input().split())) for _ in range(N)]
    res = assignroom(meeting)
    print(res)

Uploaded by Notion2Tistory v1.1.0