백준 파이썬 1931 회의실 배정

백준 링크:https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

그리드, 정렬을 이용한 풀이를 했다.

import sys

n=int(input())
li=[list(map(int,sys.stdin.readline().split())) for i in range(n)]
li.sort()
cnt=0
for i in range(n):
    result = 1
    temp = li[i][1]
    for j in range(i+1,n):
        if temp > li[j][0]:
            continue
        else:
            temp += (li[j][1]-li[j][0])
            result += 1
    if cnt < result :
        cnt = result
print(cnt)

이중 for in문을 돌려서 시간복잡도가 미친듯이 돌아간다. 100001 * 50000은 해야하나???

너무끔찍한 풀이였다.

 

그래서 for in문을 하나로 압축하는 방식으로 생각해서

import sys

n=int(input())
li=[list(map(int,sys.stdin.readline().split())) for i in range(n)]
li.sort(key= lambda x: (x[1],x[0]))
a,s=0,0
for i,j in li:
    if a <= i:
        s += 1
        a = j
print(s)

먼저 끝나는 순으로 정렬 한 후

만약 x[1]이 x+1[0] 보다 작다면 카운터를 올리고 x+1[1]로 반복

설명이 더 어렵네..