회의실 배정

문제

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

제한사항

입출력 예

풀이

function solution(meeting) {
  let answer = 0;
  // 끝나는 시간이 빠른 기준으로 정렬, 끝나는 시간이 같다면 시작시간이 빠른 순으로 정렬해야한다.
  meeting.sort((a, b) => {
    if (a[1] === b[1]) return a[0] - b[0];
    return a[1] - b[1];
  });
  let endTime = 0;
  for (let x of meeting) {
    if (x[0] >= endTime) {
      answer++;
      endTime = x[1];
    }
  }
  return answer;
}

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

• 그리디 문제이다. 그리디문제는 정렬을 했을 때 해결에 도움이 되는 경우가 많다.

• 이문제의 경우 회의가 끝나는 시간이 빠른 기준으로 정렬을 해야한다.

• 끝나는 시간 오름차순으로 정렬을 해두고 시작시간과 끝나는 시간을 비교해가며 count해주면 답을 구할 수 있다.

• 알고리즘을 풀 때 항상 해결을 어떤식으로 할지 명확하게 생각을 해두고 그 과정을 코드로 옮기는 식으로 접근해야 막무가네 식 풀이를 피할 수 있다. 고민하자!