[백준] 1931 회의실배정 - javascript

📌 문제

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

📌 풀이

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

let n = Number(input[0]);
let arr = new Array(n + 1);
for (let i = 0; i < n; i++) {
  arr[i + 1] = input[i + 1].split(" ").map(Number);
}
arr.sort((a, b) => (a[1] === b[1] ? a[0] - b[0] : a[1] - b[1]));
let cur = arr[0][1];
let ans = 1;
for (let i = 1; i < n; i++) {
  if (arr[i][0] >= cur) {
    cur = arr[i][1];
    ans++;
  }
}
console.log(ans);

✔ 알고리즘 : 그리디

✔ 끝시간 기준으로 정렬하여 시간이 안겹치게 카운트해주면 된다.

❗ 정렬할 때 시작시간을 고려하지 않고 끝시간만을 고려하여

arr.sort((a, b) => a[1] - b[1]);

이런식으로 정렬을 해서 풀었더니 88%쯤에서 틀렸습니다 를 받았다.
반례로는

3
3 3
3 3
1 3
답 : 3

처럼 cur이 3으로 바뀌면서 1 3 회의를 참석하지 못하게처리되어 답이 2로 출력되는것을 확인할 수 있었다.

이를 고치기 위해서는 정렬할때 끝시간이 같으면 시작시간 빠른게 앞에오도록

arr.sort((a, b) => (a[1] === b[1] ? a[0] - b[0] : a[1] - b[1]));

이런 방식으로 구현해야 맞았습니다 를 받을 수 있다

✔ 난이도 : 백준 기준 실버1