BOJ - 회의실 배정

문제

BOJ — 회의실 배정

접근 방법

한 회의실에 겹치지 않게 배정할 수 있는 회의의 최대 개수를 구한다. 회의가 끝나는 시각과 다음 회의가 시작하는 시각은 같아도 된다.

회의를 종료 시각의 오름차순으로 정렬하고, 종료 시각이 같으면 시작 시각의 오름차순으로 정렬한다. 마지막으로 선택한 회의의 종료 시각 이후에 시작하는 회의를 순서대로 선택한다.

가능한 회의 중 가장 일찍 끝나는 회의를 선택하면 이후 회의를 배정할 시간이 가장 많이 남는다. 다른 회의로 시작하는 최적 배정이 있더라도 첫 회의를 가장 빨리 끝나는 회의로 바꿔 나머지 회의를 유지할 수 있으므로 이 선택을 반복해도 최대 개수를 얻는다.

시작 시각을 보조 정렬 기준으로 사용하는 이유는 길이가 0인 회의 때문이다. 종료 시각이 같은 (1, 2), (2, 2)를 이 순서로 처리하면 두 회의를 모두 선택할 수 있다. 반대 순서이면 (1, 2)를 선택하지 못한다.

코드

const fs = require('fs')
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number)
const n = input[0]
const meetings = []
for (let i = 0; i < n; i++) {
  meetings.push([input[1 + 2 * i], input[2 + 2 * i]])
}
meetings.sort((a, b) => a[1] - b[1] || a[0] - b[0])

let answer = 0
let lastEnd = -Infinity
for (const [start, end] of meetings) {
  if (start >= lastEnd) {
    answer += 1
    lastEnd = end
  }
}
console.log(answer)

복잡도와 경계 조건

회의 수가 n이면 시간은 정렬을 포함해 O(n log n), 추가 공간은 O(n)이다.

회의가 하나인 경우, 종료 시각이 같은 회의들, 시작과 종료 시각이 같은 회의들을 확인한다. 입력은 공백 단위로 읽어 줄바꿈 형식에 의존하지 않는다.