결혼식

문제

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

제한사항

입출력 예

풀이

function solution(times) {
  let answer = Number.MIN_SAFE_INTEGER;
  let timeLine = [];
  for (let x of times) {
    timeLine.push([x[0], 0]); // 들어오는 시간
    timeLine.push([x[1], 1]); // 나가는 시간
  }
  timeLine.sort((a, b) => {
    if (a[0] === b[0]) return b[1] - a[1];
    // 만약 14시에 들어오는 사람이있고 나가는 사람이 있으면 나가는 사람이 먼저
    else return a[0] - b[0];
  });
  console.log(timeLine);
  let count = 0;
  for (let x of timeLine) {
    if (x[1] === 0) {
      count++;
    } else {
      count--;
    }
    answer = Math.max(answer, count);
  }
  return answer;
}

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

// 들어오는 이벤트와 나가는 이벤트로 나눈다.
// 시간 순으로 정렬을 하되 같은 들어오는 시간과 나가는 시간이 같으면 나가는 이벤트를 먼저 오게한다.

• 그리디 문제이다.
• 들어오는 이벤트와 나가는 이벤트로 나눠 하나의 배열에 넣고 시간 순으로 정렬한다.
• 이때 시간이 같다면 0보단 1이 먼저 즉 나가는 이벤트가 먼저 오게해야한다.