1931번. 회의실 배정(정렬 알고리즘)

문제

---

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

---

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

---

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

문제 요소 파악

---

이 문제의 핵심은 정렬이다.
우선 나는 2차원 리스트 안 리스트에 1번 인덱스를 sort()하고 그 다음 0번 인덱스를 sort()하기로 했다.

이유는 0번 인덱스(회의 시작시간)와 1번 인덱스(회의 종료시간)를 비교해야 하는데, 회의 종료시간이 정렬이 되어 있어야 정리가 편할 것 같아서이다. (우선 무작정 해보는거지 뭐..)

# 2차원 리스트를 만들어주는 list comprehension
li = [list(map(int, input().split())) for _ in range(int(input()))]
# sort를 위한 lambda식. 
# 1번 인덱스로 sort()하고 그 안에서 1번끼리 충돌날 경우 0번 인덱스로 비교하여 sort()
li = sorted(li, key=lambda x : (x[1], x[0]))

[[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]

토대는 마련 되었으니, 이제 생각을 해야한다.

그리디 알고리즘 키워드가 붙었으니, while을 무제한으로 돌려서 1번 인덱스보다 작거나 같은 0번은 다 없애보는게 어떨까?

4보다 작은 3,0(1,2번 인덱스)은 지우고! 다음 7보다 작은 3,5,6을 지워보는 것이다!

i = 0
while True:
    if li[i][1] >= li[i+1][0]: 
        del li[i+1]
    else: i += 1
    if i == len(li) -1: break
print(len(li))

진짜 좀 쳤다.. 싶었는데

개같이 멸망하였다.

생각해보니 아래 if문 설정이 조금 약해서 그런 것 같다. 다음에 보완하도록 하자..

이번엔 이차원 리스트 두개를 다 뽑아서 시작 시간과 종료시간을 계속 비교해보는 것으로 해본다.

i = 0
last = 0

for start, end in li:
    if last <= start:
        i += 1
        last = end
print(i)

결과는 대 성공!

저 방식을 설명하자면 시작 인덱스가 last보다 크거나 같으면 즉, 회의를 할 수 있는 시간이 되면 + 1을 해준다.

어떻게 해도 회의는 1번은 진행할 수 있는 점을 노렸다.

그 후 last를 종료시간(4)으로 바꾸고 종료시간(4)보다 작은 start들은 걸러낸 후 크거나 같은게 나오면 위와 같이 또 바꿔준다.

그런 식으로 하다보면 4개가 나온다.

start : 1  last : 0 # 여기서 start가 더 크니 i+=1, last는 start에 붙었는 애로!
start : 3  last : 4
start : 0  last : 4
start : 5  last : 4  # start가 더 크니 이때 i += 1, last는 start에 붙어있는 애로 변경!
start : 3  last : 7
start : 5  last : 7
start : 6  last : 7
start : 8  last : 7 # 여기서 또 start가 더 크니 i+=1!
start : 8  last : 11
start : 2  last : 11
start : 12  last : 11 # 여기서도 i+=1. 근데 이제 for문 종료되니까 끝

이런 느낌?

최종 코드

li = [list(map(int, input().split())) for _ in range(int(input()))]
li = sorted(li, key=lambda x : (x[1], x[0]))
i = 0
last = 0

for start, end in li:
    if last <= start:
        i += 1
        last = end
print(i)

읽어주셔서 감사합니다!