백준/ Silver 1 문제 , 백준 파이썬 1931 , 회의실 배정 [그리디]

백준/ Silver 1 문제 , 백준 파이썬 1931 , 회의실 배정 [그리디]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
시간차이가 가장 적은 것들이 최적의 해라고 생각했는데 반례가 생겼다. 이후로 코드 수정해서 반례는 해결했지만, 막상 돌려보니 시간초과.
시간차이로 접근하면 안되고 1. 회의가 끝나는 시각 2. 회의 시작 시각 을 순위로 정렬해서 처리해야한다.

 

 

문제 출처

 

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

 

풀이

 

 

1. 기본 세팅

 

1. N 입력 받기

 

2. N 행의 리스트 입력받기

 

 

2. 정렬

 

1. 회의가 끝나는 시각

 

2. 회의가 시작되는 시각

 

이 우선순위로 정렬 한다.

 

 

이렇게 정렬이 되면

 

1 3

2 2

2 2

2 2

 

이런 입력이 입력될 시 시작 시각과 끝나는 시각이 같은 회의들을 우선적으로 카운트 할 수 있게 된다.

 

참고로 시작 시각과 끝나는 시각이 같은 회의는 카운트에 반드시 포함되어야 최다의 회의 갯수를 가질 수 있다.

 

 

3. 카운트 및 처리

 

정렬된 첫번째 원소는 무조건 포함되며, 이 값을 기준으로 끝나는점과 다음 시작점을 비교해준다.

 

조건에 만족하면 카운트해주며 end 값을 변경해가며, for 문을 돌려주면 최다의 회의실 갯수를 카운트할 수 있다.

 

 

 

 

 

반례

 

3
1 10
9 12
11 20

정답: 2

 

 

5
6 7
6 6
5 6
5 5
7 7

정답: 5

 

 

 

5
1 9
2 8
3 7
4 6
5 5

정답: 1

 

 

 

 

 

정답

 

 

import sys
input=sys.stdin.readline

N=int(input())
l=[list(map(int,input().split())) for _ in range(N)]
l.sort(key=lambda x:(x[1], x[0]))
end=0
cnt=0
for i in range(N):
    if l[i][0]>=end:
        cnt+=1
        end=l[i][1]

print(cnt)