2022/03/21) 8. 회의실 배정 [정렬과 그리디, 결정알고리즘]
1. 문제
<회의실 배정>
: 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한 번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
2. 해결 방법
- 이 문제는 끝나는 시간으로 정렬(그리디)해야한다.(회의 시간이 몇 시간인지 등 이런 것들로도 정렬할 수 있겠지만, 이게 제일 탁월한 방법이다. 그리고 끝나는 시간이 같을 경우엔 시작 시간으로 정렬해 준다.
- 변수 et를 선언해서 0으로 초기화해준 후, x[0]이 et보다 크거나 같으면, answer++을 해준 후 et에 x[1]값을 넣어준다.
3. 정답
<script> function solution(meeting){ let answer=0; meeting.sort((a, b)=>{ if(a[1]===b[1]) return a[0]-b[0]; else return a[1]-b[1]; }) let et=0; for(let x of meeting){ if(x[0]>=et){ answer++; et=x[1]; } } return answer; } let arr=[[1, 4], [2, 3], [3, 5], [4, 6], [5, 7]]; console.log(solution(arr)); </script>
4. 후기
왜 끝나는 시간으로 정렬하는지 이해가 안갔는데, 유투브에서 귀류법으로 설명해주는 걸 보니 조금 이해가 갈 거 같긴 하다. 복습할 때 이 논리를 다시 정리하도록 하자.
Author And Source
이 문제에 관하여(2022/03/21) 8. 회의실 배정 [정렬과 그리디, 결정알고리즘]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@7lo9ve3/20220321-8.-회의실-배정-정렬과-그리디-결정알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)