BOJ - 1931 회의실 배정

문제 링크 : https://www.acmicpc.net/problem/1931

문제 티어 : 실버1 

문제 유형: 그리디 알고리즘

문제 풀이: 회의실을 최대한 많이 쓰기 위해선 시간이 겹치지 않아야 한다. 즉 이전 회의 종료 시간보다 다음 회의 시작 시간이 크면 된다. 이를 나타내면 아래와 같다.

 

ex) 1 - 4 / 5 - 7 / 8 - 10 (O) 

      1 - 4 / 2 - 5 / 6 - 10 (X) 

 

따라서 1 , 4 이 부분을 좌표로 만들어주면 어떨까 생각했다. 즉, (1,4) 라고 설정하고 (x1,y1) 이라 생각하기로 했다.

위 경우를 일반화 시키면 아래와 같다. 

(x1,y1) = (1,4) // 첫 번째 입력 값

if x2가 y1보다 크면 

  count++ ; // 회의할 수 있는 회의 갯수 증가

 

그러나 경우의 수를 따져보니 이 경우 발생할 수 있는 문제는 첫 번째 입력값을 (x1,y1)으로 셋팅했을 때 첫 번째 값이 생각보다 크면 그 뒤 회의들을 먼저 넣었으면 들어갈 수 있었던 것들도 못 넣는 문제가 발생할 것 같았다. 

 

그래서 정렬을 해주기로 했고 어떤 기준으로 정렬해주냐를 생각해보았다. 

예제 입력에서 종료 시점 기준으로 정렬되어 있길래 왜 그런지 생각해보았고 확실히 이전 회의 종료 시점과 현재 회의 시작 시점을 비교해야 하니 종료 시점으로 정렬 해주는 것이 좋다고 생각이 들었다. 만약 종료 시점이 같은 경우에는 시작 시점을 기준으로 정렬을 해주면 되겠단 생각이 들었다. 그 후 로직은 위와 동일한 방식으로 구현될 것이라 생각했다. 

 

문제 코드

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]);
lett arr = [];
for(let i=1;i<=n;i++){
   arr.push(input[i].split(" ").map(Number));
 }
 
 // 정렬 
 function compare(a,b){
     if(a[1]!==b[1]) return a[1]-b[1];
     else return a[0]-b[0];
}

arr.sort(compare);

// 값 비교 
let count = 0; // 회의 갯수 들어갈 변수
let endTime = 0; // 현재 회의 종료 시간
for(let i=0;i<arr.length;i++){
    if(arr[i][0]>=endTime) {
        endTime = a[i][1];
        count+=1;
        }
}
console.log(count);