회의실 배정 (그리디 알고리즘)

문제

한 개의 회의실이 있다. 이를 이용하고자 n개의 회의에 대하여 회의실 시간표를 만드려고 한다.
각 회의 시간에 시작시간과 끝시간이 주어지고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.
회의는 한번 시작하면 중단 할 수 없으며, 한 회의가 끝나는 동시에 다음 회의가 시작될 수 있다.

입력설명:
첫째 줄은 회의의 수(n)이다. 
둘째 줄부터 n+1줄까지 각 회의 정보인데, 공백을 사이에 두고 시작시작과 끝시간이 주어진다.
회의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)이다.

입력예제 1
5 
1 4
2 3 
3 5 
4 6
5 7
출력예제 1 - 첫째 줄에 최대 사용할 수 있는 회의 수 출력
3
예제설명 (2, 3), (3, 5), (5, 7)이 회의실을 이용할 수 있다.

입력예제 2
3 
3 3 
1 3 
2 3
출력예제 2 
2
예제설명 (1, 3), (3, 3) 이 회의실을 이용할 수 있다.

 

 

풀이

1. solution 함수에 입력받은 meeting인자의 끝나는 시간을 오름차순으로 정렬한다.

1-1. 만약 meeting인자의 sort메서드 과정중에 끝나는 시간이 같다면, 시작시간을 기준으로 오름차순으로 정렬한다.

2. 처음 끝나는 시간을 0으로 변수(el)설정한다.

3. 정렬된 meeting 배열을 반복 순회 한다.

3-1. 만약 시작 시간이 끝나는 시간(el)보다 크거나 같을땐 answer를 1 올려주고 끝나는 시간(el)을 지금 요소의 끝나는 시간으로 바꿔준다.

 

 

 

코드

function solution(meeting){
  let answer = 0;
  meeting.sort((a, b) => { // 1
    if (a[1] === b[1]) return a[0]-b[0]  // 1-1
    return a[1]-b[1]
  })
  console.log(meeting) // [ [2, 3],[1, 4],[3, 5],[4, 6],[5, 7] ]
  let el = 0;  // 2
  for (let x of meeting) {  // 3
    if (x[0] >= el) {  // 3-1
      answer++;
      el = x[1];
    }
  }

  return answer;
}

let arr=[[1, 4], [2, 3], [3, 5], [4, 6], [5, 7]];
console.log(solution(arr));
// let arr2 = [[3,3], [1,3], [2,3]]
// console.log(solution(arr2))

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의

 

Reference

[백준1931] 회의실 배정 (그리디 알고리즘) : https://www.acmicpc.net/problem/1931

---

 

탐욕법(그리디) 알고리즘

 

JavaScript로 greedy algorithm(탐욕 알고리즘) 구현하기