PostsSeriesLabsAlgo

그리디

회의실 배정

끝나는 시간이 빠른 것부터

회의실은 하나이고 회의 여섯 개가 신청돼 있습니다. 막대는 그 회의가 차지하는 시간입니다.
겹치지 않게 가장 많은 회의를 잡으세요. 끝나는 시각에 다른 회의가 시작하는 건 겹치지 않습니다.

세 방법 가운데 가장 많이 잡는 방법은 무엇일까요? 먼저 골라 보세요.

고른 회의 0개

내 예상 · 실제 끝나는 시간이 빠른 것부터 (3개) → 달랐어요

B 10~11시 → C 11~15시 → F 15~20시내가 고른 회의는 0개였습니다. 시작이 빠른 순은 0개, 짧은 순은 0개, 끝나는 시간 순은 0개(B · C · F)를 잡았습니다.

시작이 빠른 순1개
짧은 순2개
끝나는 시간 순3개
같은 회의 여섯 개입니다. 고르는 기준만 다릅니다.
  • 고르는 방법 — 끝나는 시간이 가장 빠른 회의부터. 이미 고른 회의와 겹치지 않을 때만 고른다
  • 이유 — 일찍 끝날수록 뒤에 남는 시간이 많다. 남는 시간이 많을수록 회의가 더 들어간다

지금 가장 좋아 보이는 것을 고르고 되돌아보지 않는 방법 = 그리디. 거스름돈에서 큰 동전부터 주는 것과 같은 생각입니다.

이 문제의 이름은 회의실 배정(활동 선택)입니다.

고르는 기준이 맞아야 가장 많이 잡힌다

  • 시작이 빠른 순 — 가장 먼저 시작한 A(9~16시)가 긴 시간을 혼자 차지해 나머지를 막는다. 1개
  • 짧은 순 — 가장 짧은 B(10~11시) 다음에 E(13~16시)를 고르면 C(11~15시)와 F(15~20시)가 둘 다 겹친다. 2개
  • 끝나는 시간 순 — 어떤 입력에서도 가장 많이 잡힌다. 가장 먼저 끝나는 회의를 고르면 뒤에 남는 시간이 가장 길다. 3개
  • ① 에서 본 것 — 시작 순과 짧은 순이 진 자리가 바로 반례다. 기준을 바꾸면 결과가 달라진다

코드는 끝나는 시간으로 줄 세운 뒤 한 번 훑는 것이 전부다

다음을 눌러 한 줄씩 넘기며 노란 선(지금까지 고른 회의의 끝)이 오른쪽으로 가는 걸 보세요.

다음을 눌러 한 줄씩 넘겨 보세요

max_meetings.py
  1. 1def max_meetings(meetings):
  2. 2 meetings.sort(key=lambda m: (m[1], m[0]))
  3. 3 count = 0
  4. 4 end = 0
  5. 5 for s, e in meetings:
  6. 6 if s >= end:
  7. 7 count += 1
  8. 8 end = e
  9. 9 return count
0 / 23

23스텝입니다. 2번 줄에서 회의 순서가 곧바로 끝나는 시간 순으로 바뀝니다. 회의 이름(A~F)은 처음 순서이고, 그림의 줄 순서가 정렬된 순서입니다.

  • key=lambda m: (m[1], m[0]) — 끝나는 시간으로 줄 세운다. 끝이 같으면 시작이 빠른 쪽이 먼저
  • if s >= end — 시작이 지금 끝 이후일 때만 고른다. 끝과 시작이 맞닿아도 고른다
  • end = e — 고른 회의의 끝이 새 기준이 된다

정렬이 일의 대부분입니다. 회의가 100,000개면 약 1,660,964번이고 1초 안에 끝납니다.

회의 C(11~15시)를 지우면, 같은 코드는 회의를 몇 개 잡을까요?

회의실 배정에서 틀리는 자리

  • 정렬 기준을 시작 시간으로 하면 — 이 회의들에서 코드가 1개만 잡는다(제대로는 3개). 일찍 시작한 긴 회의가 나머지를 막는다
  • 정렬을 안 하면 — 입력 순서대로 훑어서 이 회의들에서는 1개가 나온다. 끝나는 시간 순으로 세워야 한다
  • s > end 로 쓰면 — 끝과 시작이 맞닿은 회의를 놓친다. (1, 2)와 (2, 3)이면 1개인데 제대로는 2개다
  • 끝이 같을 때 시작 순이 없으면 — 시작과 끝이 같은 0분 회의가 있는 문제에서 틀린다. (3, 3)과 (1, 3)이면 1개인데 제대로는 2개다. 그래서 키가 (m[1], m[0]) 이다

문제에서 이 말이 보이면

겹치지 않게 최대 개수회의실 배정·스케줄끝나는 시간 순으로 정렬

다음 장에서는 가능한 경우를 빠짐없이 만들어 보는 순열과 조합을 봅니다.