백준 - 1931번

import sys

n = int(sys.stdin.readline())

arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

meeting = []

for i in range(arr[0][0],arr[0][1]+1):
    meeting.append(i)

cnt = 1

if n > 0:
    for i in range(1, n):
        if meeting[-1] == arr[i][0]:
            for j in range(arr[i][0] + 1, arr[i][1] + 1):
                meeting.append(j)
            cnt = cnt + 1
            continue

        elif meeting[-1] < arr[i][0]:
            for j in range(arr[i][0], arr[i][1] + 1):
                meeting.append(j)
            cnt = cnt + 1
            continue

        elif meeting[0] == arr[i][1]:
            for j in range(arr[i][0], arr[i][1]):
                meeting.append(j)
            cnt = cnt + 1
            continue

        elif meeting[0] > arr[i][1]:
            for j in range(arr[i][0], arr[i][1] + 1):
                meeting.append(j)
            cnt = cnt + 1
            continue
elif n == 0:
    cnt = 0

print(cnt)

메모리 제한이 걸려버렸다.

 

import sys
n = int(sys.stdin.readline())

time = [[0]*2 for _ in range(n)]
for i in range(n):
    s, e = map(int, sys.stdin.readline().split())
    time[i][0] = s
    time[i][1] = e

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


cnt = 1
end_time = time[0][1]
for i in range(1, n):
    if time[i][0] >= end_time:
        cnt += 1
        end_time = time[i][1]
print(cnt)

계산방법은 맞았지만 중요한걸 하나 놓쳤었다.

그리디 알고리즘은 순서를 생각하지 않고 하기 때문에 내가 먼저 순서를 정해주어야한다.

따라서 lambda 를 통해서 시작시간 기준으로 오름차순으로 하고 끝시간을 기준으로 다시 오름차순을 했다.

이제 겹치는 부분이 있는지만 조건문과 반복문을 통해서 만들어주면 답이 나온다.