[JS] 백준 1931 회의실 배정 자바스크립트 node.js 풀이

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

 

---

옛날에 풀었던 건데 또 같은 이유로 헷갈렸다. 

 

풀이

 

1. 미팅을 많이 하려면 끝시간이 빠른 것부터 확정지어주면 된다,

-> 그래서 배열을 끝시간을 기준으로 정렬해준다.

!!!!!!!!!!!!그런데 이때! 만약 끝시간이 같다면, 시작 시간도 오름차순으로 정렬을 해줘야 한다!

반례 예시

3
1 2
3 3
2 3

// 정담 : 3
// 끝시간만 정렬 했을 경우 : 2

 

2. CofirmedMeetings라는 배열 안에 가능한 미팅을 넣어주면서, 배열의 마지막(확정된 회의)과 비교 대상 회의들의 첫 시간 값을 비교해서, 회의가 가능하면(이전 끝시간 <= 지금 시작시간) 배열에 push한다.

3. CofirmedMeetings 배열 개수만 세어주면 됨.

const filePath = process.platform === 'linux' ? 
'/dev/stdin' : './input.txt';

let input = require('fs').readFileSync(filePath).toString().trim().split('\n');

let meetingCnt = Number(input[0]);
let meetingArr = []
// 미팅 배열 넣기
for(let i=1; i<= meetingCnt;i++) meetingArr.push(input[i].trim().split(" ").map(Number))


// 미팅을 최대한 많이 하려면, 시작 시간은 중요하지 않고 일단 끝나는 시간이 빨라야 한다.
// 끝나는 시간 순으로 정렬해서 탐색하고, 다음 첫 시간이 끝시간보다 같거나 나중이라면 바로 채택.

// meetingArr을 내부 배열의 [1]번째 값 기준으로 정렬해야 함. 
meetingArr = meetingArr.sort((a,b)=>{
    // 끝 시간을 기준으로 정렬해주세요.
    if(a[1]===b[1]){ //근데 끝시간이 같다면, 시작 시간으로 봐주세요.
        return a[0] - b[0];
    }else{
        return a[1]-b[1];
    }
    })
let confirmedMeetings = [meetingArr[0]]
for (let i=1; i<meetingCnt; i++){
    let lastMeeting = confirmedMeetings[confirmedMeetings.length-1]
    if( lastMeeting[1] <= meetingArr[i][0]){
        confirmedMeetings.push(meetingArr[i])
    }
}
console.log(confirmedMeetings.length)