백준 1931번 회의실 배정 [그리드 알고리즘]

백준 1931번 회의실 배정

한 개의 회의실이 있고, 이를 사용하고자 하는 N개의 회의에 대한 사용표를 만들어야 한다.
각 회의의 값에서는 시작시간과 끝나는 시간이 주어지고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대 사용 횟수를 구하자.

 

[문제풀의과정]

1. 주어진 회의 정보에는 회의의 시작시간과 종료시간이 주어진다.

2. 시작 시간이 아무리 빠르더라도 종료 시간이 늦는다면, 이후에 선택 할 수 있는 회의의 수가 줄어 들 수 있다.

3. 즉 가장 빨리 끝나는 회의를 먼저 선택하는 그리드 문제로 볼 수 있다.

4. 정렬을 하는데 종료시간을 기준으로 오름차순으로 정렬하고,

현재 진행중인 회의시간의 종료시간과 다음 시작 시간의 값을 비교하는 방식으로 구현을 진행하였다.

 

[코드]

counts = int(input())

time_tables = []
for _ in range(counts):
    start,end = map(int,input().split())
    time_tables.append((start,end))

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

current_end_time = 0
result = 0
for start_time, end_time in time_tables:
    if start_time >= current_end_time:
        result+=1
        current_end_time = end_time
        
print(result)