백준 1931 파이썬(그리디)

백준1931 파이썬 

 

맨 처음 풀었던 내 코드 

전체 시간을 집합(set)으로 만들어주고 거기에서 차집합으로 하나하나 빼가면서 검사를 했다.

시간초과가 떠서 새로운 방법을 생각해보아야 했다.

아마도 for문이 중복되는 부분이 있어서 입력값이 커질경우 연산량이 많아지기 때문일 것이다.

O(n^2)

 

# 회의실 - 시간초과
# big o 표기법에서 어떻게 되는건지

n = int(input())
conf = []
time = set()
for i in range(n):
    start, end = map(int,input().split())
    conf.append([start,end,abs(start-end)])
    for j in range(start,end+1):
        time.add(j)

conf.sort(key=lambda x:x[2]) # 2차원 리스트 정렬

count = 0
for i in conf:
    temp = {j for j in range(i[0],i[1])}
    if temp.issubset(time):
        count += 1
        time = time.difference(temp)
print(count)

 

두번째 시도 

회의시간이 짧은 것부터 처리해야된다고 생각해서

끝나는 시간 기준으로 오름차순

시작시간 기준으로 내림차순

이렇게 정렬한다음 검사해보았다.

결과는 틀렸습니다.

예외가 어떤 케이스가 있는지 생각해보니

[1,4],[4,4]같이 시작하자마자 끝나버리는 회의가 있는 경우 경우

count가 1로 되어버리는 문제가 생긴다.

 

# 회의실
n = int(input())

conf = []
for i in range(n):
    start, end = map(int,input().split())
    conf.append([start,end])
conf.sort(key=lambda x:(x[0],-x[1]))

count = 0
last = 0
for i,j in conf:
    if i >= last:
        count += 1
        last = j
print(count)

 

마지막 시도

사실은 내가 처음부터 생각해낸건 아니고 구글링 한 코드이다.

끝나는시간도 오름차순으로 정렬하였다.

[1,4],[4,4]같은 경우도 count=2로 처리하여 정답이 되었다

 

# 회의실 문제
n = int(input())

conf = []
for i in range(n):
    start, end = map(int,input().split())
    conf.append([start,end])
conf = sorted(conf,key=lambda x:x[0])
conf = sorted(conf,key=lambda x:x[1])

count = 0
last = 0
for i,j in conf:
    if i >= last:
        count += 1
        last = j
print(count)