[그리디/백준] 1931번: 회의실 배정

-문제:https://www.acmicpc.net/problem/1931

 

-정답 풀이: 

처음에는 i와 i-1의 회의만 비교했는데, 그렇게 하면 조건 만족하지만 멀리 떨어져있는 회의들끼리는 비교할 수가 없다. 

그래서 조건 만족하는 회의들을 모아놓고 싶었는데, 그게 잘 안됐다. 

 

이전 회의 끝난 시간은 last에 저장해서 비교하면된다. 

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split()))) 
data.sort(key=lambda x : x[0])    
data.sort(key=lambda x : x[1])
count=0
last=0
for i,j in data:
    if i>=last:
        count+=1
        last=j
print(count)

 

-시도해본 풀이:

이렇게 풀면 시간초과가 난다

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split()))) 
data.sort(key=lambda x : x[0])    
data.sort(key=lambda x : x[1])
count=0
answer=0
for i in range(n):
    for j in range(i+1):
        if data[i][1]<=data[j][0]:
            count+=1
    answer=max(count,answer)
            
print(answer)