[BOJ] 1931번 - 회의실 배정

🔥 접근

1. 해당 문제는 그리디를 이용하여 아래 아이디어를 기반으로 문제를 접근하였다.
   • 가능한 한 많은 회의를 선택하려면, 빨리 끝나는 회의부터 우선 선택하는 것이 유리하다.
   • 빨리 끝나는 회의를 선택해야 그 이후에 더 많은 회의를 배치할 수 있기 때문!
2. 회의 정보를 종료 시간을 기준으로 정렬한다.
   • 종료 시간이 빠른 순서로 정렬
   • 만약 종료 시간이 같다면, 시작 시간이 빠른 순으로 정렬 (예: (1, 2) vs (2, 2) → (1, 2) 우선)
3. 정렬된 회의 리스트를 순회하면서, 이전 회의가 끝난 시간 이후에 시작되는 회의를 선택합니다.

🧑‍💻 코드

const fs = require('fs');

const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const input = fs.readFileSync(filePath, 'utf8').toString().trim().split('\n');

const N = Number(input.shift());

// 1. 가장 먼저 끝나는 것으로 정렬
// 2. 끝나는 시간이 같다면 시작시간이 작은 것으로 정렬
const arr = input
  .map((item) => item.split(' ').map(Number))
  .sort((a, b) => {
    if (a[1] === b[1]) return a[0] - b[0];
    return a[1] - b[1];
  });

// 3. 시간이 되는 것 중에서 가장 빨리 시작하는 것 선택
let time = 0;
const select = [];

for (let i = 0; i < arr.length; i++) {
  if (time > arr[i][0]) continue;
  select.push(arr[i]);
  time = arr[i][1];
}

console.log(select.length);

🔗 관련 링크

• https://www.acmicpc.net/problem/1931