[백준] 1931번 회의실 배정 [Python] - 정렬

 

 

회의실 사용표 시간을 보고

이어서 사용할 수 있는 최대 회의의 수 구하는 문제

 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

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

 

끝나는 시간 순서대로 정렬

현재 회의끝나는 시간 <= 다음 회의 시작 시간 -> 다음 회의 이용 가능!

다음 회의 사용하고, 위의  방식을 반복하며 추가로 이용 가능한 회의 찾기

import sys
def f():
    N = int(sys.stdin.readline())
    c, e = 0, 0
    # 끝나는 시간 순서대로 오름차순 정렬, 끝나는 시간이 같으면 시작 시간 순서대로 오름차순 정렬
    for a, b in sorted([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)], key=lambda x: (x[1], x[0])):
        # 다음 회의 시작 시간이 현재 회의 끝나는 시간 보다 크거나 같으면 다음 회의 선택
        # 끝나는 시간 업데이트, count +1
        if e <= a:
            e = b
            c += 1
    print(c)
if __name__ == "__main__": f()

 

지저분해서 별로 안 좋지만,

e:=b, 이 표현으로 값을 업데이트하는 연습입니다.

import sys
def f(e=0):
    N = int(sys.stdin.readline())
    # (e:=b) 끝나는 시간 업데이트
    print(sum((e:=b) and 1 for a, b in sorted([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)], key=lambda x: (x[1], x[0])) if e <= a))
if __name__ == "__main__": f()

 

sys.stdin.readline 대신 open$($0$)$를 사용해서 작성한 코드입니다.

def f(c=0):
    a = open(0)
    _, *li = map(int, a.read().split())
    print(sum((c:=e) and 1 for e, s in sorted(zip(li[1::2], li[::2])) if c <= s))
if __name__ == "__main__": f()

 

예제 입력 1 

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1 

4

 

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.