← 9주차 · 그리디
보통그리디정렬

회의실 배정

각 원소가 [시작, 끝]인 회의 배열 meetings가 주어져요. 회의실은 하나뿐이고, 한 회의가 끝난 시각에 다른 회의가 시작하는 건 겹치지 않는 것으로 봐요(끝나는 시각 = 다음 시작 시각 허용).

겹치지 않게 배정할 수 있는 회의의 최대 개수를 반환해요.

핵심은 끝나는 시각이 빠른 회의부터 고르는 거예요. 빨리 끝날수록 뒤에 남는 시간이 많아 더 많은 회의를 넣을 수 있어요. 시작이 빠른 순이나 짧은 순으로 고르면 반례가 생겨요.

예시

예시 1
입력
meetings = [[1, 4], [2, 3], [3, 5], [5, 6]]
출력
3
설명
[2, 3] → [3, 5] → [5, 6]을 고르면 3개예요. [1, 4]는 [2, 3]과 겹쳐요.
예시 2
입력
meetings = [[0, 2], [1, 3], [2, 4]]
출력
2
설명
[0, 2] → [2, 4]를 고르면 2개예요.

제한 사항

  • 1 ≤ meetings.length ≤ 100,000
  • 0 ≤ 시작 < 끝 ≤ 1,000,000,000
끝나는 시각 기준으로 정렬한 뒤, lastEnd를 두고 현재 회의의 시작이 lastEnd 이상이면 고르고 lastEnd를 그 회의의 끝으로 갱신해요.
javascript
function meetingRooms(meetings) {
  const sorted = [...meetings].sort((a, b) => a[1] - b[1]);
  let count = 0;
  let lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) {
      count++;
      lastEnd = end;
    }
  }
  return count;
}
이전 문제거스름돈 최소 동전 (배수 화폐)
다음 문제구명보트
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.