❓❓❓ ★★★회의실 배정 : Greedy Algorithm

Hint

• 빨리 끝나야 빨리 회의를 시작할 수 있으므로, 끝나는 시간 기준으로 정렬을 한다.

• 시작시간 순으로 정렬
  : 먼저 시작했지만 겁나 긴 경우 때문에 X

• 회의 길이 순으로 정렬
  : 중간에 애매하게 겹치는 경우 때문에 X

내 풀이 : 재귀함수

function solution(meeting) {
  let answer = 0;
  meeting = meeting.sort((a, b) => {
    if (a[1] === b[1]) return a[0] - b[0];
    else return a[1] - b[1];
  });
  let select = [0, 0];
  for (let i = 0; i < meeting.length; i++) {
    if (select[1] <= meeting[i][0]) {
      select = meeting[i];
      answer++;
    }
  }
  return answer;
}

let arr = [
  [1, 4],
  [2, 3],
  [3, 5],
  [4, 6],
  [5, 7]
];

console.log(solution(arr));

solution의 접근법을 듣고도 겨우 풀었음 ㅠㅠ

Solution 풀이

  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));

훨씬 풀이가 깔끔하다 ㅠㅠ
결국엔 끝나는 시간이 중요하기 때문에 !!
끝나는 시간을 기준으로 비교하는 것이 맞는 것 같다 !!

배운 점

Greedy 알고리즘 에 대해 살짝 감을 잡은 것 같다 !!