[Algorithm] [Python&Swift] 백준/BOJ - 1931 _ 회의실배정

1931 - 회의실배정

 

문제

---

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

 

입력

---

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

 

출력

---

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

 

제출코드

---

Python

def greedy(arr):
    count = 0
    start_time = 0
    for time in arr:
        if time[0] >= start_time:
            count += 1
            start_time = time[1]
    return count

n = int(input())
arr = [list(map(int ,input().split())) for _ in range(n)]
arr.sort(key=lambda x:(x[1], x[0]))
print(greedy(arr))

 

Swift

func greedy(arr: [[Int]]) -> Int {
    var startTime = 0
    var count = 0
    for time in arr {
        if time[0] >= startTime {
            startTime = time[1]
            count += 1
        }
    }

    return count
}
let n = Int(readLine()!)!
var arr = [[Int]]()
for _ in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{ Int($0)! })
}
arr.sort { (a,b) -> Bool in
    if a[1] == b[1] {
        return a[0] < b[0]
    } else {
        return a[1] < b[1]
    }
}
print(greedy(arr: arr))

 

문제풀이

---

문제의 핵심은 정렬이다.

어떠한 방법으로 정렬을 진행해야 원하는 순서대로 값을 정렬할 수 있는지 파악하면 문제는 바로 풀린다.

최대한 많은 회의를 진행하기 위해서는 우선적으로 회의가 시작하는 시간이 아닌 회의가 끝나는 시간을 기준으로 정렬해야한다.

예를 들어, [1, 10], [3, 5], [4, 8], [2, 3] 으로 값이 주어졌을때, 회의 시작 시간을 기준으로 정렬하면 아래와 같은 결과가 나온다.

[1,10], [2, 3], [3, 5], [4, 8] -> 따라서 첫번째 회의 이외에는 아무것도 진행하지 못한다.

반대로 회의가 끝나는 시간을 기준으로 정렬하면 아래와 같은 결과가 나온다.

[2, 3], [3, 5], [4, 8], [1, 10] -> 이와 같이 진행할 경우 총 3개의 회의를 진행할 수 있다.

따라서, 회의가 끝나는 시간을 우선하여 정렬을 진행하며 만일 끝나는 시간이 동일한 경우를 대비하여 추가적으로 회의 시작 시간이 일찍인 순서대로 정렬을 진행한다.