[그리디]결혼식

문제

현수는 다음 달에 결혼을 합니다. 현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.
피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다. 각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다. 현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.

(만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다)

 

문제풀이

• 이벤트가 start(참석시간)과 end(떠난시간) 두 개로 나뉜다.
• 각 시간과 해당 시간에 일어난 이벤트를 한 쌍으로 새로운 자료구조를 생성한다.
• 기본적으로 시간 순서대로 정렬을 하되, 만약에 시간이 똑같다면 이벤트를 비교하여 정렬한다.
• 이벤트 비교 시, 이벤트에 먼저 도착한 친구가 떠난 시간이 앞으로 와야되고 새로 온 친구가 참석한 시간이 뒤로 정렬되어야 한다.

코드

function solution(...times) {
  let answer = Number.MIN_SAFE_INTEGER;
  let timeLine = [];
  
  for(let x of times) { //참석시간과 떠난시간 두 이벤트와 각 시간으로 나눈다.
    timeLine.push([x[0], 's']); 
    timeLine.push([x[1], 'e']); 
  }
  timeLine.sort((a, b) => {
    if(a[0] === b[0]) return a[1].charCodeAt() - b[1].charCodeAt(); //시간이 같다면 이벤트 종류에 따라 나눈다(아스키코드 사용)
    else return a[0] - b[0]; //기본적으로 시간 순대로 정렬
  })
  let cnt = 0;
  for(let x of timeLine) {
    if(x[1] === 's') cnt++;
    else if(x[1] === 'e') cnt--;
    answer = Math.max(answer, cnt);
  }
  return answer;
}

console.log(solution([14, 18], [12, 15], [15, 20], [20, 30], [5, 14]));