백준 1931 회의실 배정 : 파이썬

 

import sys
input = sys.stdin.readline

N = int(input())
time = []

for i in range(N):
  start, end = map(int,input().split())
  time.append((start, end))

time.sort(key=lambda x : (x[1], x[0]))

cnt = 1
end = time[0][1]

for i in range(1, N):
  if time[i][0] >= end:
    end = time[i][1]
    cnt += 1

print(cnt)

---

회의가 빨리 끝나게 되면 남은 회의 시간이 많아서 더 많은 회의를 할 수 있다.

그래서 빨리 끝나는 순서대로 회의 시간을 정렬한다.

time.sort(key=lambda x : (x[1], x[0]))

두 번째 값(x[1])을 먼저, 첫 번째 값(x[0])을 그 다음 기준으로 삼아 정렬하는 방식

x[1]이 회의 종료시간이기 때문에 회의가 빨리 끝나는 순서대로 정렬되게 됨

(이 과정에서 요소 자체는 변하지 않고, 정렬 기준만 달라지는 것)

---

정렬된 회의시간을 반복해서 다음 회의 시작 시간 >= 이전 회의 끝나는 시간 을 만족할 때 해당 회의를 진행하도록 한다.

for i in range(1, N):
  if time[i][0] >= end:
    end = time[i][1]
    cnt += 1

이미 회의가 빨리 끝나는대로 정렬되어 있기 때문에 회의 시간이 겹치지 않도록 조건만 걸어준다.

겹치지 않을 때, 해당 회의 끝나는 시간을 end에 넣어서 다음 조건을 실행할 수 있게하고

회의 횟수 cnt를 더한다