백준 1931번 회의실

링크

1931번: 회의실 배정

회의실은 한개고

회의실의 시간들이 입력됩니다.

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 

 

참고로 끝나는 시간의 입력은 오름차순이 아니에요

8 12

1 3

이런식으로 입력이 될수도있어요

근데 예제입력을 보면 끝나는시간이 오름차순이라

맞왜틀이 나오면 끝나는 시간으로 오름차순 정렬을 안하지않았나 확인해보세요

 

문제 해석

3 4

2 5

7 9

2 3

시간이 이렇게 있으면

우리는 겹치지않게 하면서 최대한 많은 회의 할수있게 만들어야합니다.

일단 끝나는 시간을 기준으로 오름차순으로 정렬을 해야합니다

왜냐면 끝나는 시간이 빨라야지 다음 회의를 더 많이 진행할수있으니까

 

[ [3 ,4] , [2 ,5] , [7,9] , [2,3]]

 

이렇게 되어있죠

이걸 오름차순으로 정렬해보면

[2,3] [3,4] [2,5] [7,9]

이렇게 정렬할수있습니다.

여기서 겹치지않게 뽑아낸다면

2 3

3 4

7 9

이렇게 배정해줄수있겠죠

여기서 겹치지 않는다는건

2시에 시작해서 3시에 끝나면

다음 회의의 시작하는 시간이 3시거나 3시보다 커야한다는겁니다.

그래서[2,3] [3,4] [2,5] [7,9] 이건

회의를 3개할수있으니까

정답은 3

 

정답코드 Python

case = int(input())
times = []
count = 1 #한개의 회의는 무조건 할수있으니까 1부터시작 

for i in range(case):
    time = list(map(int,input().split(' ')))
    times.append(time)

times.sort(key = lambda x: (x[1], x[0])) #끝나는시간으로 오름차순정렬 배열안에 배열이 들어있음

endTime = times[0][1] #정렬하고 나서 첫 회의의 끝나는 시간 

for T in range(1,len(times)): #두번째 회의부터 마지막 회의까지
    st = times[T][0] #시작시간
    et = times[T][1] #끝나는 시간
    if st >= endTime: #endTime보다 크거나 같으면 겹치지않는 회의라는거니까
        count += 1 #회의의 갯수 하나 올려줍니다
        endTime = et 
print(count)