[백준 1931] 회의실 배정
February 26, 2023
문제
https://www.acmicpc.net/problem/1931
아이디어
기본적으로 종료 시간이 빠른 회의를 먼저 진행해야 최대한 많은 회의를 할 수 있는 가능성이 있기에 종료 시간을 기준으로 정렬을 해야 한다.
그런데, 종료 시간이 같다면 시작 시간이 더 빠른 회의를 먼저 진행해야 한다. 만약 (7, 8) (6, 8)의 두 회의가 있다면 시작 시간이 더 빠른 후자의 회의를 먼저 진행해야 더 많은 회의를 할 수 있다. 그렇기에 종료 시간이 같다면 시작 시간이 더 빠른 회의를 앞쪽으로 정렬해야 한다. 즉, 정렬 기준은 다음과 같다.
- 종료 시간이 빠른 회의가 앞에 와야 함.
- 종료 시간이 같다면, 시작 시간이 빠른 회의가 앞에 와야 함.
이렇게 정렬만 되어 있다면 회의를 순차적으로 진행하면서 이전의 회의가 끝났으면 새로운 회의를 진행시키면서 카운트를 기록하면 된다.
소스코드
// 입력 처리
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const n = Number(input[0]);
const arr = input.slice(1, n + 1).map(e => e.split(' ').map(e => Number(e))).sort(
(a, b) => {
if (a[1] !== b[1]) return a[1] - b[1]; // 기본적으로 종료 시간이 빠른게 앞에 오도록 정렬함.
else return a[0] - b[0]; // 만약 종료 시간이 같다면 시작 시간이 빠른게 앞에 오도록 정렬함.
});
// 문제
function solution() {
let time = arr[0][1]; // 가장 일찍 끝나는 맨 첫번째 회의 먼저 진행시킴.
let count = 1;
// 두번째 회의부터 스케줄 체크.
for (let i = 1; i < n; i++) {
const [start, end] = arr[i];
// 만약 현재 회의의 시작 시간이 이전에 진행중이던 회의의 종료 시간 이후라면, 회의를 진행할 수 있으므로 진행시킴.
if (start >= time) {
time = end;
count++;
}
}
console.log(count);
}
// 실행
solution();